The full-text search feature of MySQL, which is generally available on any shared hosting environment, is a great way to add this kind of functionality. The only downside is that it works only on MyISAM tables which have generally been deprecated in favor of InnoDB.
The approach that I have seen work, where a great example is the Wikipedia database architecture, is to create derivative copies of model records specifically for searching purposes. These need to be kept in sync with the main record, but that's easily done with an after_save handler or a simple SQL update statement.
One note is that ActiveRecord is not capable of understanding full-text indexes. A rather ugly extension is required to make it cooperate, though I do have an example bundled up in a collection of MySQL hacks:
http://github.com/theworkinggroup/rails_mysql_hacks/tree/master