In my opinion, you'd be daft to build your own search from scratch. Google are the world experts on search; leave them to do the hard work.
Some people dislike having Google branding on their website search, because it makes them look "cheap" or "amateur". I disagree: Google is a popular brand; users
like Google, and they trust it to work. Having Google branding on your search box is a
good thing, because users will trust the quality of the search.
Google is the obvious choice; unless you have a compelling reason to use something else, use Google.
Google offer several search packages:
I don't like Adsense for search, because it uses invalid code. This breaks the validation of my web pages and consequently makes it very difficult to know when I've made a coding error.
I think the best option is the free Google custom search engine (CSE). This is much like Adsense for search, except the code is
almost valid and can be made valid with the addition of a <div> or two. The
terms of service on Adsense are draconian: you must not modify the code. That does not seem to be true for Google CSE.
The main "drawback" to Google CSE is that, unlike Adsense, you
must have a Google logo somewhere in you search area. I like the subtle "faded Google logo inside text box" option.
A really neat feature is that you can make the search results appear on your site, not on a Google page. So you get Google search results within the "frame" of your site, with your branding and navigation.
Moreover, you can include Google ads on the search results page. You can link your CSE account to your Adsense account, so you'll get paid for clicks on your CSE ads. This effectively converts CSE into Adsense, but without the crappy code.
Google CSE business edition costs money: at least $100 per year. The main "benefit" over the free version seems to be that you can dispense with the Google branding. Personally, I don't see this as a benefit: I think Google branding inspires confidence in your search.
Google allows you to customise the colours of all these search options, but you don't have complete control. For example, you cannot change the search box colour using CSS: it's all hard-coded.