O'Reilly's CGI Programming with Perl has a chapter on searching your web sites. The upcoming second edition is pretty good (but it won't be published for another month or so). Have a look at the previous version for some ideas.

The search button here at Perl Monks is a little different. Since all nodes are stored in a database, the query goes to a SQL statement searching the comprehensive node index for titles similar to the query.