First publish free app (light version) with admob ads and some limitations, than use House Ads(AdMob mechanism) to promote Your paid app in your free app FOR FREE! Try to publish on friday - Your app will be longer on top of New App. Use Your keywords in title, description and put your own comment with keywords. If You want paid advertising use Admob - cheaper and good targeting. Good quality graphics for app market site is very good idea. And this is not theory, I'm using it for my apps.