Search vs. Traversing Hierarchies vs. Browsing

When users have time they like to browse relevant content, especially when doing so on the big-screen devices. If you can, try to distinguish the gender of your user as the search patterns differ. 
When users try to buy something but they don't know the exact name they might select from the general category, but they might not have patience to traverse several levels.
When users they know what they want they might search for it, but they will type the keyword only once, especially when doing so on the virtual keyboard.
The summary of the behavior is as follows: have the search field right on top of the home screen, it could be only an icon that when clicked opens into an input field, remember that Android phones already have the search button, however tablets might not. In addition to search offer selector menu to filter the results. Once they use either one, or both you should start showing relevant results and let them browse. You could detect if they are pleased with the results and chance the suggestions accordingly. A simple hot, or not ("thumbs up or down") functionality would do the job.
Displaying relevant content and other related products on the bottom so user can keep on going without searching again is usually a good solution.
Finally, remembering user previous searches is very important, especially ability to change slightly the spelling of the previous search.

Uki's Google Java Technology blog