I work with one client that really hurt themselves with a site search. We've fixed some of the problems, but here's the heads up on possible issues we uncovered:
Consider this -- a new visitor searches a word or phrase, and if they get no results, you may have lost them immediately. In this case, you are worse off than not having a search utility. It can be like advertising the site's weakness, instead of adding a strength.
In order to be successful, a site search often needs to be a bit "fuzzy". That is, it should at least account for common misspellings and synonyms that are not literally in your copy, and return useful pages to your visitor.
Building and maintaining a top-end fuzzy search solution can consume time and money, but it's worth considering if the client is serious about doing business on the web. One of the best site searches I've ever used is at Amazon -- I'm sure they threw major resources into it, and continue to do so. Every reasonable search I do there returns SOME suggestion, no matter how I mangle the spelling.
One of the most useful things about site search is the ability to log unsuccessful searches. At the very least, the site owners get a report of what their users are looking for. If the design allows it, you can also modify your lookup and add in these unsuccessful search terms and some related pages that weren't pcked up by the literal indexing. This adds a practical degree of fuzziness. You can also write the terms into your content and re-index.
One last comment, sites who have a search function often allow that fact to excuse them from maintaining sound information architecture and navigation. It's a temptation that can kill site stickiness in relatively short period of time.
Given these caveats, if the site has the resources, I suggest outsourcing the search function. One of my clients uses FreeFind to good success. They offer a range of services beginning at free and going up to high end enterprise solutions. I haven't tried their high end service, but given the strength of their free and minimally priced offerings, I think they are a strong operation.