Amazon CloudSearch - Start Searching in One Hour for Less Than $100 / Month
You know this doesn't seem like a bad deal though $100/mo might be high for someone just starting out. Right now my options for search are:  Full text SQL search
  Apache Solr or something similar
  Google Search Appliance
  Custom search
  Google free search on your site

Yay for search as a service.