I think a textbox would actually be preferred for this. A select box doesn't invite typing - so it becomes a bit of a hidden trick to filter it (not to mention that Firefox will pretty much do it right anyway).
You can easily throw an image next to a textbox to indicate that it has options, which allows both mouse driven or keyboard driven interaction.
I'm partial to JQuery, so I'd use JQuery's autocomplete - which has config options to require a match, or that clicking the box will drop down all items.
If you're interested in "progressive enhancement", you may be best off with both a traditional select input (for accessibility) that gets replaced by an autocomplete textbox driven off the same data. Something like:
<select id="s">
<option value="foo">Foo</value>
<option value="bar">Bar</value>
</select>
var d = $('#s OPTION').map(function() {
return $(this).text();
});
$('#s').hide().append('<input type="text" />')
.autocomplete(d, {
mustMatch: true,
minChars: 0,
autoFill: true,
matchContains: false
})
.result(function(e, d, f) {
// Select option for the form to submit
$('#s').val(d);
});
You could also leave the select visible - which makes it more flexible, but potentially more confusing - and hook an event handler to the select box to update the textbox as well so that they stay in sync.