You have a couple of options for search in ruby world like
- Sphinx
- Ferret
- Solr
- Endeca
Going through the documentation of heroku, heroku suggests with solr which is an awesome search engine. http://docs.heroku.com/websolr and http://docs.heroku.com/full-text-search details more information about that. We chose solr for search in one of our projects and we used sunspot_rails which nicely integrates with your models and reindexes when your content changes. We used the gem sunspot_rails from http://github.com/outoftime/sunspot which is recommended by heroku too.
Caveat though is that heroku's file system is read only and does not allow you to run arbitrary processes, so you have to choose one like websolr(starts from 20$ a month) or spawning your own amazon ec2 instance and do the indexing there. Since heroku is also running on amazon ec2, the latency is very very less.
Getting back to the alternatives, Ferret is known to crash/corrupt indexes often in production. Sphinx is not supported by heroku. Endeca is damn expensive, you gotta spend most of your budget just even to get basic results.