There are a number of ways to do it -- the Sphinx module, Lucene module. I prefer to just use Google search. You're not going to beat their search algorithms. You have to pay a nominal fee if you want to skin it, but it's worth it for the search power.
Here's an example of a site that's built out with all dataobjects, and you can see we use Google for the global search function.
Hi Uncle Cheese
Nice work with the Custom Google Search
I am testing integration of a custom Google search and can do so with results be shown on the same page as the KW input search field
(by extending a page type)
What method are you using to have the search input form available on all pages and output to a separate search results page?
An alternative to Google : a widget proposed by Exalead ([url]http://www.exalead.com/search/widgets/search/generate/[/url])
You can test it on one of my websites if you like : [url]http://anafin.fr/[/url]
Just one drawback : you can't customize the results page. But it's free and it works very well !