Let's see... I find new apps....
1) Amazon AppStore's Free App of the Day. Really, it's about the only thing I do with their store since Amazon's update policy causes apps to lag behind those on the Play Store. However, since I check this daily, it's my first line of discovering new apps -- or at least new crappy, bug-ridden, intrusive, IAP-greedy games...since that's about 95% of the FAOTD offers.
2) Sites like here, Gizmodo and Engadget which regularly or semi-regularly publish "App of the Week" articles.
3) Sales. This usually applies to games, but occasionally other types of apps announce sales and either get featured in the Play Store or get a feature article on one of the above-mentioned sites. I use the Play Store daily as well, but that's usually just to get the nigh-daily app updates. When I remember, I check the front page for deals.
4) XDA Developers Forums. I will occasionally troll the Apps and Themes sections for my devices looking for cool new stuff.
5) Word of mouth. This is practically a last resort. My wife is pretty good about telling me about the latest cute puzzle game for her iPhone...for all the good that usually does me. My Android-using friends are pretty mum about apps. Maybe they're not app junkies like I am?