A couple of ideas spring to mind, some of them you well already be using and I'm sorry if some of them seem obvious.
Are you in fact Filtering rather than Searching?
Check that your database tables INDEXES are maximised
Use the mysql LIMIT clause so you only fetch 10 rows at a time.
Identify which are the popular searches, concentrate on caching them. (do you record the filter terms? If this uses the GET method to filter, you might be able to grep through your logfiles looking for patterns of popular filter terms).
If you are using the GET method to handle your filtered data, installing a semi-automated opcode cache like APC might help.
When deciding what to cache, consider whether you want to cache just the data, or a html segment with containing the data set formatted ready to be slotted straight into the template of your page.
Make sure you are clear about how often the data changes, this may dictate how long the cache has to live "ttl" (time to live)
This isn't a checklist BTW, just a couple of thoughts you might want consider.