I've been developing Android Apps close to 2 years now and have already had some experience in the field of trying and promoting my apps.
I've stepped on a few rakes along the way and I thought it would be a good idea to share my thoughts and experiences.
1. Advertising.
I've used 3 ways of advertising my apps. 2 of which include admob, the other includes AppBrain.
Here is what I have learned:
Doing basic banner ads on AdMob has provved uneffective in terms of money spent/money earned. A budget of 200 usd dollars blows by in a matter of minutes, results in a lot of clicks but few installs. And the installs that do come generally don't result in any significant increase in income. Neither do they reflect upon the placement of the app in the Play Market.
The only way to make it work is to use careful targeting. Target a small audience, a specific app market. To get anywahere in USA you need a hefty advertising budget. And since results arent as clear as they should be this could be a risky. What I did was attempt to target a certain age group in a certain region based on languages. Also I looked at where my app was actually used and tried to stimulate those markets by trying and bringing it up higher in search results.
So far my marketing using this has been a failure. I determine that simply - I've spent more on advertising than I've gained. So obviously thats a failure.
2. In House ads. They prove to be effective in increasing the user base slightly, but really hit your earnings. And for in house ads to work you also need to have an app that has lots of users. This is kinda of a closed loop, so it might work if you have a popular app.
3. AppBrain - you pay for install. This has worked better than AdMob, but I feel paying 0.4 usd per install is rather risky. And I doubt that in the end I will get the money back.
What works best for me?
Cross advertise between your apps. Have a section or pull down bar in every app that shows of your other apps. This seems to be wroking!
2. Paid reviews
So I've done a couple of paid reviews. And they dont work. AndroidTapp for example charges 150usd for a review. I never get that money back. I get a 1-2 day boost, earn about 20 usd and thats about it. The only way I see that helping is if you spend lots of money and do a paid review on many sites at the same time and this could boost your app and it could go higher up in the store rankings.
So my advice to you is - dont bother with paid reviews. They dont work.
3. Social Media
This sort of wakrs for me but it requires a lot of work from my side. Genrally I target communities or groups in Google+, Facebook and other social sites. I do post a couple of tweets and so on. Each outburst of this advertising results in about 150-200 installs. Best of all its free for you and you see a certain gain.
4. Press releases and sites that do them
Press release sites like pitchpigeon didnt do a thing for me. For 50 usd all I got back was emails from paid review sites wanting more moeny for reviewing my game. So this has also been an utter waste of my resources.
Summary
Being an indie developer is tough. The market has saturated and big players spend lots of money on promotion. The sums they use and have on hand is something beyond any indie developer can use for marketing of their app. So all I can tell you is use social media. Spam like hell but be careful and follow guidelines. Promoting and marketing an app is just as tough as actually making one.