I think it depends on how "serious" you're about your search.
If you just want to search in some simple VARCHAR fields, which you'd manually do by generating some "LIKE '%xyz%'" statements, than all you need is a plugin that does that for you. My favourite here is searchlogic. It enables quite a few handy dynamic scopes in your models, which you can chain together (like other scopes). For example you can write something like this:
User.last_name_like("Doe").age_gt(30).age_lt(40)
Here's a great screencast on how to use its other features.
But SQL LIKE statement isn't really a good fit for searching in large chunks of text. So if that's what you need, you'd be better of using a plugin that actually indexes your data.
In that case thinking sphinx (mentioned in other answers) is a great solution. Just keep in mind that it requires some platform specific installation steps and only works with PostreSQL and MySQL (it doesn't work with Rails' default SQLite). Using it is also not that straightforward - you need to define what to index on every model you want to search, build the index, start Sphinx, etc.