Free, Open Source and Low Cost Search Engines

Generally there are compromises here. You'll either have to do a bit more work, or it may not have all the features you'd ever want. But these will certainly satisfy enough requirements for some sites.

Open Source

Lucene / Nutch / Solr / Carrot^2
Geared towards programmers and techies.
lucene.apache.org/
lucene.apache.org/nutch/
lucene.apache.org/solr/
project.carrot2.org/

Hybrid: Open Source with Company Add Ons

Flax
www.flax.co.uk which is based on Xapian

Xapian
www.xapian.org
 

Tesuji
www.tesuji.eu

Smila
www.eclipse.org/smila
wiki.eclipse.org/SMILA

Free: Commercial

Free IBM/Yahoo Offering
"IBM OmniFind Yahoo! Edition" up to 500,000 documents, admin GUI, synonyms
omnifind.ibm.yahoo.net

Hosted

FreeFind
Year after year FreeFind provides a great service at a low price (though not free if you want to remove the ads). Consider it for small public sites; certainly not "search 2.0".
www.freefind.com

Google Free (Hosted)
Uses the index Google already has of public web sites.
www.google.com/faq_freewebsearch.html

Higher End Commercial Solutions

If none of the above tools work, you might want to check out the Search Vendor Directory