That's because App Store search is extremely lame and in need of as major overhaul.

you have to use the direct link

https://itunes.apple.com/app/gmail/id422689480

obviously a search for gmail should work, but as you discovered, it doesn't, unless Apple have fixed it by now.