Make a great game
This is the most fundamental thing that will affect your position in app store search results . Unless you have a compelling game that is fun to play the rest of the techniques in this post won't work. If you have a great game but still aren't getting many downloads, then read on.
There is also something to be said here about the category of the game you are creating. If you make a game that is already in a crowded category then you are going to have a much harder time becoming visible. My games so far have fitted in to the "Cards and Casino" games category and it appears to be much easier to stand out there than in the "Arcade and Action" category for example.
Another factor that helped my own success was a gap in the market for a European style slot machine game. Prior to releasing Cherry Chaser there were a hundred "Vegas" style slots games but none that simulated European pub style games.
Target specific search keywords
If at all possible, include your most desired search keywords in to the title of your game. The Google Play store's search algorithm appears to put the highest weighting on the app title. This is why Super Snake is called "Super Snake Slot Machine" on the Play store. This also helps prospective users to quickly identify what sort of game it is.
In your apps description try to repeat the search terms that you want to target multiple times. In the description of Super Snake I use the term "slot machine" five times. I avoid using the terms superfluously as I suspect that Google have some sort of intelligence in their algorithm that ignores terms that are repeated too many times in quick succession.
Think about all the variants of your search term that people might use and then add those in to your description as well. I have a sentence that reads "If you like slot machines, one armed bandits or pokies, you'll love this game." which is included entirely for this purpose.
For the first week after I released Cherry Chaser the app store icon was anonymous. Nothing about the icon gave any hint as to the nature of the game and it looked very similar to every other icon next to it. At that point I changed to my current "fruit machine cabinet" icon and downloads of the game began to increase dramatically.
The new icon informs the person browsing the store about the nature of the game and the departure from the conventional rounded rectangle shape makes the icon stand out on the page.
I still use the original rounded rectangle icon for the launcher on the phone because the purpose is different. Icons on phones should look consistent and aesthetically pleasing and standing out in that context would be a negative for the game.
Target other languages
The Google Play store has a feature that allows you to auto-translate your listing into a large number of other languages. The only reason you should not use this feature is if you already know the language in question and can do a better job yourself. Even if you can speak the language you're targeting the auto-translate feature will probably give you a good basis from which to work.
My games have done extremely well in European countries such as Germany and Spain and that is due to auto-translated descriptions. I have had one customer point out that the games auto-translated description in German is bad bordering on the ridiculous, but I'm still getting far more downloads than if I had nothing in there.
Encourage long term engagement
A major factor in your position in the Play Store is the ratio of downloads to active installations. You could have a million downloads but if every user is uninstalling your app after ten minutes, Google will see that as being a bad sign about the quality of your game.
My solution to this problem was the addition of achievements as a game device. There is a reason that achievements have become ubiquitous in gaming and that is because they work. They trigger the part of the human psyche that says "challenge accepted!". Adding these into my games increased my user engagement enormously which had a positive effect on my active installation ratio and improved my search ranking.
The final piece of advice is to get your game reviewed and rated by as many of your players as possible. The higher your star rating the higher you will be on the search results. Put a link to the app store's review function somewhere in your app to make it as easy as possible for your user to rate your app.
Be careful about where and when you make the suggestion to review the app. I have used apps in the past that ask me to review them before I've even used them - bad idea. A common technique is to wait for a number of plays and then suggest that the player might want to now give the game a review.
My preference is to ask the player to rate my game when they have just won an achievement. It's fairly obvious that they will probably be feeling quite good about themselves and the game at this point so it seems like the best time to ask. So far this has been working out very well for me and all my apps have 4.5 star ratings in the store.