I'm quite partial to having one dedicated site search page, and then linking to it on the main pages, rather than putting a big old empty text box on every page -- that just begs for some filling in. When I've changed site to this approach, their stats usually go up significantly, unless their Information Architecure really sucks, but that's a whole other thread.
Using site search logs is SUCH a big help for a site. Hannamyluv has nailed it -- and it only hurts in for the first few months or so. Also, you can get some great ideas for new products, articles and even Information Architecture changes.
I started a thread 4 years ago on this topic -- it still has some good stuff in it for today: