What kind of publicly available search software is able to be purchased or used freely as part of a website, and how good is it?
There are plenty of good open source options—Solr is currently my favourite. It’s extremely powerful but you do need to do some programming on top of it—I use Django and Haystack to build the search UI on most of my projects.
We use the Solr+Haystack combination for our search feature on http://lanyrd.com/search/
If you don’t want to run custom software on your own server there are plenty of options too—Google’s Customised Search is very popular: http://www.google.co.uk/cse/