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':
Yes they certainly do cache certain combinations, depending on your language. They also have an entire database containing a lot of possible typo’s for each word, so they autosuggest stuff even when you’ve spelled it wrong. This indeed costs a lot of processing, but then again: google has a ton of servers with a lot of processing power.