Si quisiera crear algo como esto desde cero, usaría algo llamado TF/IDF:frecuencia de término/frecuencia de documento inversa. Eso significa que, para simplificarlo enormemente, encuentra palabras en la consulta que son poco comunes en el corpus como un todo y encuentra documentos que contienen esas palabras.
En otras palabras, si alguien ingresa una consulta con las palabras "Quiero comprar un elefante", entonces de las palabras en la consulta, la palabra "elefante" es probablemente la palabra menos común en su corpus. "Comprar" es probablemente el siguiente. Por lo tanto, clasifica los documentos (en su caso, consultas anteriores) por cuánto contienen la palabra "elefante" y luego cuánto contienen la palabra "comprar". Las palabras "yo", "a" y "un" probablemente estén en una lista de palabras sueltas, por lo que las ignora por completo. Clasifica cada documento (consulta anterior, en su caso) según la cantidad de palabras coincidentes que hay (ponderación según la frecuencia inversa del documento, es decir, peso alto para palabras poco comunes) y muestra las primeras.
He simplificado demasiado, y necesitarías leer sobre esto para hacerlo bien, pero en realidad no es muy complicado de implementar de una manera simple. La página de Wikipedia podría ser un buen lugar para comenzar:
http://en.wikipedia.org/wiki/Tf%E2%80 %93idf
