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?