The search box works as follows:
It separates the words based on any word separator, including space or comma or quote marks, etc... (see QA_PREG_INDEX_WORD_SEPARATOR and $qa_utf8punctuation in qa-util-string.php).
Each of these words is then matched against any of the following:
* Title of question
* Tag of question
* Content of question, answer or comment
* Handle of user asking question
The matches are weighted based on (1/frequency in database) so that a match of a word that appears 100 times in a particular way is worth half of a word that appears 50 times. If the word appears more than 10000 times in the database in a particular way it is ignored (this value can be changed in QA_IGNORED_WORDS_FREQ in qa-config.php).
There is also additional weighting as follows:
* Let's say a title match is worth 1 (if the word appears several times in the title it's still just worth 1)
* Tag match is worth 2 (since it's an explicit indication by the user)
* Question content match is worth 0.5 to 1 depending on frequency of word in the question content
* Answer content match is worth 0.25 to 0.5
* Comment content match is worth 0.125 to 0.25
* User handle match is worth 1
For each question, these values are added up, with any matches for an answer or comment counting towards the parent question. Questions are then shown from the search in order of their total score.
This is all done through a single fast (but rather complex!) MySQL query, built in qa_db_search_posts_selectspec(...) in qa-db-selects.php.
As to your question, AND and OR aren't so relevant, since words in the search string that match nothing are simply ignored. This is unlike search engines like Google. The reason is that the search needs to work for people entering whole questions, as well as individual words, and the sentence for a whole question is very likely to have words that match nothing.
The search does not yet support other sorts of advanced features you mention. I'm not sure they will all be in such high demand, but in general improving the search function is certainly there on the roadmap.