How can I advertise my app on the App Store?
You can link to apps in the appstore. For example:

http://itunes.apple.com/us/app/pinball-arcade/id455826958?mt=8

(This is just a random app I picked to serve as an example)

Now, if you have your link to your app, you can:


Write a blog about the app and link to it
Have websites review your app and they will link to it
Does your app serve the need of a particular community? Maybe they have a forum or mailinglist where you can link to your app and explain the benefits they will get from it.
Tweet, facebook or Google+ about the app