Browser search boxes are implemented in a technology called OpenSearch. See: http://www.opensearch.org/ (site currently down?)
Mozilla has a good page which explains how to implement this for their browsers: https://developer.mozilla.org/en/Creating_OpenSearch_plugins_for_Firefox While there are a few Mozilla-specific details there, that page can serve as a good starting point for cross-browser implementation.
Add auto-complete to the search box is a bit trickier. First add the auto-complete query URL as described by Mozilla. Then you must craft a response on your server which conforms to what the various browsers expect.
Take a look at what Google returns for the different browsers they support:
* Firefox: http://suggestqueries.google.com/complete/search?client=firefox&hl=en-US&q=xmarks
o Content-Type: text/javascript
o Response body: ["xmarks",["xmarksthaspot","xmarksthescot","foxmarks safari","xmark.com","gmarks firefox","x marks foxmarks","xmarksthespot","xmarks ie","foxmarks addon","foxmarks for ie"]]
* Safari: http://suggestqueries.google.com/complete/search?client=safari&hl=en-US&q=xmarks
o Content-Type: application/json
o Response body: ["xmarks",[["xmarksthaspot","18,400 results","0"],["xmarksthescot","196,000 results","1"],["foxmarks safari","148,000 results","2s"],["xmark.com","336,000 results","3s"],["gmarks firefox","50,700 results","4s"],["x marks foxmarks","13,500 results","5s"],["xmarksthespot","20,500 results","6"],["xmarks ie","96,400 results","7"],["foxmarks addon","210,000 results","8s"],["foxmarks for ie","191,000 results","9s"]]]
* Others: http://suggestqueries.google.com/complete/search?client=ie&hl=en-US&q=xmarks
o Content-Type: text/javascript
o Response body: I'm not sure it's relevant. It's essentially the exact same format as Safari above, but it's wrapped by a JavaScript call to window.google.ac.h(). I'm not 100% certain, but that looks like the callback to their HTML-page version of auto-completion and suggests to me that they don't really support opensearch auto-completion in anything but Firefox and Safari.