Yahoo! have this nifty thing whereby if you search for say, shoes, then you get a bunch of other queries to try searching for.
Now, obviously if you want to do this properly then what you want to use is some sort of Latent Semantic Indexing. But LSI engines, either Vector Space or Contextual Network Graphs, are hella slow at either indexing or searching respectively. So for a sort of throwaway feature they're not much use.
However, there's a cheats way. Basically you set up two indexes - your document index and a query index. When a query comes in then you search the document index to get the relevant documents as per normal. However then you search the query index and get a bunch of queries that match. These are you suggestions. Then you index your query (although probably only if the number of tokens in the query is between 2 and 4). The next time someone searches they'll get your query as a suggestion if their query and your query share enough terms. Obviously you can rank the suggestions by the number of times they appear.
It's cheap, quick and surprisingly effective. For t3h w1N!!11!!!1
Is the life of an internatioinal search engineer one filled with mystery, marvel and wonder ...