Google takes the stance that to search on your site, from your site, you should pay them (pricing seems fairly reasonable to me). See http://www.google.nl/enterprise/public_search.html. They'll probably block you if you try to circumvent that. You may be able to get a better deal by negotiating, but I have no experience with that.
Google Custom Search might be the solution. Free (with ads), customizable, Google search from your own pages. The business edition, as Joost says, is $100 per year and has no ads.