There are a range of solutions depending on your skills, hosting and available time.
The quickest and simplest solutions are external one's hosted by other companies but you should read their ToS as they often restrict the number of pages indexed and you may be allowing them to use your logo and name in future advertising (which wouldn't make a client pleased).
There are also solutions available for a variety of of server-side scripting languages (PHP, Perl, ASP or a mixture of them - usually different front ends to the same engine) as well as some Javascript solutions (although these tend to be a little limited).
PhpDig - I (Emperor) researched a lot of PHP search engines for the Gurus Network redesign and only this script came up to the standard I wanted and it is easy to instal.
