Функция полнотекстового поиска MySQL, которая обычно доступна в любой среде общего хостинга, является отличным способом добавить такую функциональность. Единственным недостатком является то, что он работает только с таблицами MyISAM, которые обычно не поддерживаются в пользу InnoDB.
Подход, который я видел в работе, отличным примером которого является архитектура базы данных Википедии, заключается в создании производных копий записей моделей специально для целей поиска. Их необходимо синхронизировать с основной записью, но это легко сделать с помощью обработчика after_save или простого оператора обновления SQL.
Следует отметить, что ActiveRecord не способен понимать полнотекстовые индексы. Требуется довольно уродливое расширение, чтобы заставить его взаимодействовать, хотя у меня есть пример, связанный с набором хаков MySQL:
http://github.com/theworkinggroup/rails_mysql_hacks/tree/master