Avoid short and common words
This is the most likely cause of an unexpected failed search. If your search terms include a common "stop word" (such as "the", "one", "your", "more", "right", "while", "when", "who", "which", "such", "every", "about", "onto"), then your search will fail without any results. Short numbers, and words that appear in half of all pages, will also not be found. In this case, drop those words and rerun the search.
Search is case-insensitive
The searches for "fortran", "Fortran" and "FORTRAN" all return the same results.
Words with special characters
In a search for a word with a diaeresis, such as Sint Odiliënberg, it depends whether this ë is stored as one character or as "ë". In the first case one can simply search for Odilienberg (or Odiliënberg); in the second case it can only be found by searching for Odili, euml and/or nberg. This is actually a bug that should be fixed -- the entities should be folded into their raw character equivalents so all searches on them are equivalent. See also Help:Special characters.
There is no method for searching for a phrase. Contrary to what you might expect, enclosing phrases in double quotation marks such as "can of tuna" will retrieve all pages containing "of" "tuna" and "can".
Searching limitations and Gotchas
No regular expressions or wildcards
You cannot use regular expressions or wildcards such as ? or *. If you don't know what that is, don't worry about it. To search for pages with the words "boat" or "boats" search like this: "boat or boats".
Words in single quotes
If a word appears in a page with single quotes, you can only find it if you search for the word with quotes. Since this is rarely desirable it is better to use double quotes in pages, for which this problem does not arise.
An apostrophe is identical to a single quote, therefore Mu'ammar can be found searching for exactly that (and not otherwise). A word with apostrophe s is an exception in that it can be found also searching for the word without the apostrophe and the s.
Delay in updating the search index
For reasons of efficiency and priority, very recent changes to pages are not always immediately taken into account in searches.