From this question on Microsoft Answers:
To [search] the Windows 8 Store, click the Store tile on the Start screen and then press Win+Q or touch swipe from the right edge to open charms, then use the Search charm to search for apps.
To clarify for people using a mouse:
- Open the Store
- Move your cursor to the top or bottom right corner
- Click the search icon
- Type your search