If your app has a particular market of enthusiasts (e.g.: a pet grooming app, for instance) you could seek out forums of those people and participate in those forums (constructively) while having a link to your site in your signature (if the forum allows it.)

I don't know if that's effective or not, its just an idea.

Making apps easier better to market is something we think about a lot and hope that we'll eventually have a MUCH better answer to in the future.