There's info on search including the Booleans in the FAQ (http://archiveofourown.org/archive_faqs/13) as well, and they've mentioned it in several admin posts in the last year. And if you actually do any search, the little question mark pops up there, too (not just on the tag search page).

I agree the search help could be easier for new users, but if you'd ever tried to look for it you should've been able to find it.