Search engines. My Comp Sci degree thesis. First of all you have to ask yourself the question. What type of search do you want to offer the user. If the user will clearly know what they are looking for, for example a product based website then you should provide a search engine based on meta-data. For example users will be searching for a specific product, or product type. This is generally quite easy to provide.
The next is your familiar web search engine such as Google. Google here targets a completely different market. The typical user doesn't know exactly what they are looking for. They just know that they are looking for something to do with Aeroplanes for example. Now Google has to try and figure out what is the result that is most likely to match that and be the most relevant.
I know Google has an incredibly complex and optimised system but from memory if you want to go this way you need to create something called an inverted index file. Then you need to start thinking about a thesaurus because what if the user types in cat, then you should also provide results that contain the word feline. Also word trees, because the user typed in cat the cats result will also be relevant.
I am pretty sure that if you are providing a search engine for your website then it most likely be a metadata search engine in which case you can roll your own solution. If not and you are looking for the second type then why not use Google's services. They provide a custom search that will work within your own website.