Assume you are a malware author, and you've written up some malware. Your focus has been on writing a piece of code that can run, do something, and contact you in some way across the network, without getting caught by pesky antivirus software or other security products. What that malware does probably includes stealing banking credentials, or installing adware, or some other money making mechanism. However, you've just been looking at the problem from the perspective of "I just need execution, and then I'll figure out things from there." Somehow you need that execution.

Probably the easiest way to get execution is to get someone to download and install your software. Send them an email with some social engineering saying "This is your admin and you need to run this". Maybe rename it to "document.pdf .exe" in the email. Maybe put it inside a password protected .zip file to bypass email servers that scan for viruses. To accomplish this you need to gather up a list of email addresses, and figure out how to blast out spam. Probably not too hard, but your malware will probably get picked up pretty quickly by the A/V companies and then you're going to have a much harder time getting too much of a user base. You could be more direct in who you go after and use the same techniques and that might help it last longer.

You could wrap the malware inside some app that people want (warez) and host it on a site, and try to use some SEO to get people to come to it. That's probably going to get you caught really fast too, because I'm guessing A/V companies spider the net looking for new .exe's, and once they get a copy, it's game over. Your malware gets caught and your SEO falls apart. So maybe instead you put the malware on login controlled forums where the A/V companies can't find you, or p2p sites (do people still use those?) or somewhere else where the A/V companies and other centrally controlled systems (search engines) can't block you.

Not sure how good those mechanisms are, but at some point you might try to start coding exploits to get more installs. This is going to be pretty hard though.

What you need to do is just go after one person who can get you to more people. Go after a developer who already has a large user base for his software. This is the concept behind some adware being pushed out according to an article from Kaspersky Stealing apps, installing ads. They went after an app developer, got his creds and his code, added their adware to his app, and then re-uploaded it. All the SEO was already done for them and from legit users who had previously installed the real app, and now any new downloads would get the adware.

Maybe the developer was lying. Maybe he just wanted to make a quick buck, added adware, people figured it out and companied, and then he said "Oh no, it wasn't me, I got hacked!" Maybe. I don't care much either way because now the concept is out there.

It's unclear to me if this new "updated" version of the app gets auto-updated to users. That's where you'd get the really big install base. Instead of just an android app, imagine any type of app. A windows application that can receive updates. You hack that autoupdate server, and push your malware out to hundreds of thousands of people.

Stuxnet was amazing for a couple of reasons, but one was because it was code signed. It must have looked legit to some A/V because of that. Now imagine, that a trusted app is downloading a code signed update of itself from a trusted source. Now you're cooking with fire. Not only are you getting a ton of installs, but you're bypassing tons of A/V, and the A/V companies probably aren't collecting copies of the update anyway. How many A/V companies are running honeypots with tons of common software just waiting for a malicious update to come down the intertubes? They're probably spidering the net and the browsers will get those updates, but I doubt their watching any other software, and catching a malicious autoupdate on firefox, chrome, opera, or IE would just be a side-affect of their spidering.

Germany used this same mechanism with their spyware according to a report from the H in their article German spyware exploits iTunes vulnerability. In it, Germany was apparently MiTM'ing itunes in order to get installs. This is pretty sexy. Set up an access point and let users connect and pwn them through this same technique. Or go all out and try to pwn some big internet router. I think you'll still get more bang for your buck though by going after a developer with a large user base.