How does google do the "did you mean...."?

there's several ways: Levenshtein distance, soundex, Metaphone and
Phonex algo's. There've been threads on "spelling correction" here
and in rubytalk.

A bunch of useful stuff: http://text.rubyforge.org/

Have you looked at SOLR or other full text search plug-ins.

Michael