Having written (and rewritten) my search engine about 4 times now, let me see if I can offer some info.
Many people use a radio button group with checked AND and unchecked OR choices. Then it is a simple SWITCH or IF statement to change the operator in the query. For a more elegant system, you can use a regular expression to search for AND or OR in the query string. After that, you can remove all irrelvant words (the,a,an,but...), change plurals to singular, and whatever else you need to do until you get to the heart of the question.
My suggestion is to track every search, find out how poeple are searching your site, and refine your script according to the collected data.
Best of luck. I hope this helps.