Where is the Search box?
The Search box is located above your list of emails.
It will automatically search across the entire mailbox. As you type in the search box, any contact and/or previous search term that matches will appear below as a short-cut suggestion. The screenshot below has looked at the search criteria 'j' and is asking if you want to search for all emails from Joe or Jane (as either match the criteria typed in so far) and has also found a recent search the user made 'joe's report' which matches the criteria typed. (Click on the screenshot to show full-size.)
If you wish to refine your search to the current highlighted folder, then there are further options in the navigation pane on the left of the Search box (see screenshot above).
Note: Obviously the more emails/folders you ask it to search across, the slower the search will be.
Starting the Search
Click on the magnifying glass to start the search.
Results will be shown beneath the search box and you will be able to open/close emails and return to the search view. If the results did not find the email you were looking for, you will be able to change the criteria and/or any of the search options.
If you wish to come out of the search view and go back to your normal view, where the magnifying glass was there should be a red cross, click on that cross.