If you don't want to set up Solr, or use Acquia's hosted Solr, check out this module which incorporates Zend's Lucene clone (Solr is built on Lucene):
http://drupal.org/project/luceneapi
It won't offer all the features of Solr, but it will be a lot better than Drupal's core search, and will be a lot easier / cheaper to integrate than Solr or Sphinx.
UPDATE: Actually, I just noticed this in the module description, so probably it won't work for you, at least in its current form:
Search Lucene API targets small to
medium sized web sites, usually with
less than 5,000 nodes. Because this
module is a fully integrated solution,
all search processing is handled
inside of Drupal and simply cannot
scale to large volumes of data. Going
forward, Search Lucene API will have
the option to integrate with
distributed search services such as
Elastic Search, which have the
potential of scaling up to millions of
documents.
I'm leaving the answer in place in case it helps someone else with a smaller site.