My Old Way
I've never been crazy about trying to find things in Outlook. I used to use the Advanced Find feature and I just memorized the Shift-Ctrl-F shortcut because since Microsoft went to the ribbon bar I could never find it. The only problem with this search is it takes quite a few clicks to configure as you can see in the figure. It's particularly easy to forget to enable the Search subfolders checkbox. This approach is still worth knowing but recently I've found some of the features in Outlook 2010 to be more useful in most cases.
Find the Search Box
At first discovering how to search is a bit annoying. Search as you might through the ribbon, you won't find a search tab or any search items. Seems highly bizarre to me to hide the search tab, but as I've mentioned in past posts Microsoft seems to take perverse pleasure in anti-discoverability. Maybe it's a rite of passage thing with them. Once you stop looking in the ribbon bar you will notice that for each major type of outlook item (Mail, Calendar, Contacts etc.) there is a search field. It's typically in the upper right hand corner, not too hard to find, but in my typically large Outlook window not exactly in my line of sight either. You can play hunt the search bar in the image below, but the green arrow is a big hint. Still this search method is not very effective for me.
Using the Right Search Box
The default search box limits itself to whatever folder you are currently in. That is not typically what I need when I'm searching. I have contacts divided up into multiple contact lists (otherwise all 600 contacts would sync onto my cell phone). I just want to find a person and I don't want to search across all five lists. Luckily it's easy, but it's in that hidden Search tab. When you click in the search bar the Search Tab shows up.
Microsoft highlights it in orange so you can't miss it (although I still did the first several times I searched, I don't know why, I guess I just don't expect critically useful tabs to hide themselves). It's also important to note that this tab's content will change based on which type of object you are searching for. The above image is for mail.
The one at left is for contacts. It's the All Mail Items and All Contact Items that I find the most useful. So useful in fact that I don't want them on a ribbon tab that doesn't show up. Luckily there is a solution. Right click on any item you find useful and select the Add to Quick Access Toolbar. I've already done that in the image so that option is grayed out for me, however if you look up above in the quick access bar (see the blue arrow), you can see the icon button for searching all contact items. Now whenever I want to search contacts, mail or the calendar I click the appropriate icon, Outlook automatically puts me in the search box and I start typing.
In an attempt to keep a feature for Outlook 2013, Microsoft only enables the search icon for the current section of Outlook. If you're in the contacts, you can search contacts, if you're in mail you can search mail. There appears to be no technical reason for this other than to annoy you. However, you can work around it by adding the "All Outlook Items" to the quick access bar. This works from all areas of Outlook. Happy hunting, keep an eye out for grues.