I've just uploaded a new search facility onto the site (make sure to hit Ctrl-F5 to get the new stylesheet!) and you'll see it in the secondary content to the side.
I've actually used the MSN Live Search Web Service to build it so none of the indexing is done by me and the results will be far more accurate than anything else I could have done. It's an amazingly easy web service to use (wish I could say the same for the amazon ones!) and it's dead quick too. All I do is make the request and pass the XML result through an XSL stylesheet on the search page and Bam!
I'd certianly recommend using it anyway - I'm sure plugging a web service into PHP is easy too? If you are looking for a search and your CMS doesn't provide one and you can't code I'd suggest maybe using the MSN Live Search Macros. You can basically just setup a default set of search settings and then link to your macro from your site like my one. My one only searches within my site but you can modify plenty of other settings too!
All I have to do now is get the archive links up on the site so that the bot can get to all my posts and the results will be more accurate. The only downside is that newer posts can't be searched on 'till they get looked at the the search bot but I'm not too worried about that since they are always on the front page.
Update: Built the archives at last!