In both cases (app promotion or game promotion) the key is to make people aware that you exist. If people don't know you are around, you won't be found. In both cases, you are likely competing against a lot of other sites or games.
The question to ask yourself is, where are people that would be most interested in our game? If they are playing other games, then advertising in those games is likely the best route. If they are online, then standard online advertising for your game might work. Getting links to the game (in the store or to a web-page linked to the store), could help as well, in which case all of the SEO promotion recommendations on this site can be helpful.
This is not a very good answer, but hopefully it is a start....
Lots of Software, LLC