I agree that the advanced search techniques are possible for the users who know how to use them, but I need a search box and then checkboxes for the different categories. To use marc0047's example in my site, I'd want to make two sets of boxes, one for location (Los Angeles, San Francisco, etc.) and the other for job description (Painter, Plumber, etc.). I'd want to be able to check boxes:
[x] Los Angeles
 San Francisco
So that with Los Angeles and Plumber checked, the search results would show me all jobs in L.A. for Plumbers (and not ALL jobs in L.A. or ALL Plumber jobs).
Is this beyond WordPress? If so, any suggestions on something I could use to make this work? The site in question is currently in an old MT install that I'd love to move to WP, but I do need this advanced search to work.
If someone can guide me to simple hack/plugin, I'd be much obliged. If it looks like it's a more-than-simple hack/plugin, I'm ready to talk dollars.
Thanks for any leads, links, letters, or laughs.