There are currently three search implementations for umbraco:
I would like to propose a 4th alternative Thunderstone webinator. Its a tool I used many moons ago with another CMS. It comes in 2 flavours hosted or host yourself. There is a free version it has restriction of 10,000 documents (see full version feature matrix) and only indexes html pages. I would recommend going down the hosted route, basically you create an account on the site and then point it to your website. The search engine is a crawler so all your content needs to be linked up. If you have a good site map then most if not all your content will be linked. After crawl you get your own personal url that looks like http://mysite.master.com/texis/master/search so you can create your own form that posts to that page.
The admin interface will let you style up your search results page. The results page has % relevance and find similar functionality, you can see a working result page here. I am not advocating this solution over the other excellent solutions already available I just think this is a nice alternative to give fast, rich search functionality very quickly.