<p>I want to implement search functionality for a website (assume it is similar to SO). I don't want to use Google search of stuff like that.</p>

<p>My question is:</p>

<p>How do I implement this?</p>

<p>There are two methods I am aware of:</p>

<ol>
<li>Search all the databases in the application when the user gives his query.</li>
<li>Index all the data I have and store it somewhere else and query from there (like what Google does).</li>
</ol>

<p>Can anyone tell me which way to go? What are the pros and cons?</p>

<p>Better, are there any better ways to do this?</p>

Use lucene,
http://lucene.apache.org/java/docs/
Apache Lucene is a high-performance, full-featured text search engine library written entirely in Java. It is a technology suitable for nearly any application that requires full-text search, especially cross-platform.
It is available in java and .net. It is also in available in php in the form of a zend framework module.
Lucene does what you wanted(indexing of the searched items), you have to keep track of a lucene index but it is much better than doing a database search in terms of performance. BTW, SO search is powered by lucene. :D