One of the sessions that most interested me at the Do It With Drupal thing in December 08 was Drupal Search Options led by Robert Douglas. He spoke mostly about Apache Solr and how it can be an alternative to Drupal's core search. In addition to being faster and more accurate than core search, it can perform a faceted search (like eBay, Amazon, or any number of retailer have).
A big caveat for Apach Solr in Drupal, however, is the Java requirement. Ya gotsta have Java on your server to this thing to work. In my old hosted server, I was SOL. But since I've moved to Slicehost, I can install pretty much whatever I want. So first-up on the weird-things-I-want-on-my-websites list was the Apache Solr search on my Drupal sites.
And yes I installed it and yes it works (try the search at greg-willis.com. But I didn't find any tip-to-tail installation information, so I thought I'd add my experience to help anyone looking to do what I did. The whole shebang is below the fold...