Well, it might seems trivial, but there isn't a "search" button in the Windows 8 Windows Store, so it looks like you can't search for apps.
What to do? Just start to type with the keyboard, and the search box will appear.