We launched our last night and it doesn't show up anywhere, unless we specifically look for it like this for example: "App.io" instead of just searching for "App".
What's going on? We searched all categories pertaining to the app, but nothing shows up.
On
Since your app is new it will be at the bottom of any list that there is. Google Play sorts the apps in terms of their popularity (number of downloads) even if you are searching categories. We published an app and than searched its exact name and it was still 20th on the list. As your app gets more downloads it will become more visible. Searching by category is not a great way to do it because of the vast number of apps on Google Play. If you searched games, Angry Birds has a good shot of being first while your app might not even show up at all. This is a hard stage to get past as you need downloads to move up in the lists yet it is hard to get them when Google Play users cannot access your app easily. We noticed a rather large spike of downloads on our first app once our second app gained popularity because of the "Other Apps By This Developer Section". I don't know if you have multiple apps out but if you do you will probably see an increase in downloads across all of your apps.
If I remember correctly, my app took a couple days before it was "searchable". I remember I could access it directly from the link to google play. Hope that helps, give it a day or so and it should show up.