MySQL's full-text search feature, which is usually available in any public hosting environment, is a great way to add this functionality. The only drawback is that it only works on MyISAM tables, which are usually outdated in favor of InnoDB.
The approach I saw works where a great example is the architecture of the Wikipedia database, which is to create derivative copies of model records specifically for search purposes. They need to be synchronized with the master record, but this is easy to do with the after_save handler or a simple SQL update statement.
It should be noted that ActiveRecord is not able to understand full-text indexes. To make it collaborate, a rather ugly extension is required, although I have an example compiled into the MySQL hacker collection:
http://github.com/theworkinggroup/rails_mysql_hacks/tree/master
source share