There are alot of CGI/Perl site search scripts on the web, as well as some PHP ones that I have seen, which don't require ads or banners. The CGI ones work pretty well if you can figure out how to configure them. AnologX (sorry I don't have the website address on hand) is one that I have used in the past, that wasn't too hard to configure. If you are going to be running them on a UNIX/LINUX server you will have to chmod the files and have access to the cgi/bin as well as know the path to perl on your server. The most difficult part though in my opinion is getting the templates to integrate well with the look and feel of your site. You might do a Google search and see what you find.
Depending on your site you can just use a google search. If you have a decent amount of traffic you can even get paid for your searches by using google adwords.
