Here's an amazingly thorough write-up on how Google's Autocomplete (search suggestion) feature works. From Danny Sullivan, one of the most respected of Google Watchers:

How Google Instant's Autocomplete Suggestions Work