I think he means the ‘AutoComplete’, those are the suggestions that pop up right under the input field.
The way google (and other websites) do this is by using AJAX – every time you press a key (hence: typed a letter) while focused on the input field, the google page does an XMLHTTPRequest to a server, and the response of the server is used to ‘predict’ what you’re going to search for.
In human language: Say you typed the letter H into the google search field, a request is sent to a page on the google server, and this page searches the database for everything that begins with an H. Finally, it returns the results to ‘your’ page showing the suggestions – everything the server found that starts with H (most probably limited to 5 or 10 results or so). Same goes for when you type more, so when you typed an U after the H, google’s server will look for anything that starts with HU. This all happens in about 1/10th of a second.
Using the Firebug extension you can see the requests that google performs ‘around your back’:
Hope this answers your question (I found this very interesting as well someday)