/How would you recommend implementing something like a fuzzy search with
Ruby and a SQL database.  For example, I want to search a field in a
table for anything that is similar to "Frank Smithe".  I would want an
array of matches with some sort of score telling me how good of a match
the item received ("frank smithe" 100%, "frank smith" 90%)./


Less direct, but maybe useful...
The pyLucene project is the apache java lucene library implemented in C 
and SWIG'd to python (i think).
You might be able to create ruby bindings for the full text search C 
library used there.


http://pylucene.osafoundation.org/

http://lucene.apache.org/java/docs