Se você quisesse construir algo assim do zero, usaria algo chamado TF/IDF:Term Frequency / Inverse document frequency. Isso significa que, para simplificar enormemente, você encontra palavras na consulta que são incomuns no corpus como um todo e encontra documentos que contêm essas palavras.

Em outras palavras, se alguém entrar em uma consulta com as palavras "Quero comprar um elefante", então das palavras na consulta, a palavra "elefante" é provavelmente a palavra menos comum em seu corpus. "Comprar" é provavelmente o próximo. Então você classifica os documentos (no seu caso, consultas anteriores) por quanto eles contêm a palavra "elefante" e quanto eles contêm a palavra "comprar". As palavras "eu", "para" e "um" provavelmente estão em uma lista de paradas, então você as ignora completamente. Você classifica cada documento (consulta anterior, no seu caso) por quantas palavras correspondentes existem (ponderação de acordo com a frequência inversa do documento - ou seja, alto peso para palavras incomuns) e mostra as primeiras.

Eu simplifiquei demais, e você precisaria ler sobre isso para acertar, mas não é muito complicado implementar de uma maneira simples. A página da Wikipedia pode ser um bom lugar para começar:

http://en.wikipedia.org/wiki/Tf%E2%80 %93idf