The app store has thousands of apps, with many more added each day. When you release a new app, its visibility on the app store will be brief. It might sit in the new releases section of its category for a day or two (if you're lucky). Or it might start off on page 3 to begin with, if dozens of other apps were released on the same day.
Ultimately, you can't count on the App Store itself for publicizing your app. You need to promote the app elsewhere.
Places to Announce Your App
First off, if you have a website (and you should), you'll want to set up a web page for your app and promote it on your own site. If you have a mailing list, a blog, a twitter feed, etc., post an announcement there too.
Next, you can send announcements to iPhone app sites. There are generally two types of sites: App Store scrapers, which are essentially just a mirror of the App Store itself, and news/review sites, which post original content. You generally don't need to do anything for the scraper sites; your app will show up there automatically. Review sites, however, tend to have more traffic, and don't list every app that comes out. You'll have to contact them directly.
Most of the "big" review sites won't bother to review your app, especially if you're new and unknown. But it can't hurt to try. Also, if your app is a game, you might consider creating a thread about it on the Touch Arcade Forums.
Some sites will want you to send them a promo code, so they can download your app to review it. Don't send promo codes unless a reviewer writes you back and asks for one, though. (Otherwise it might go to waste. Some sites get so many review requests, they may never even read your e-mail, much less use your promo code.)
Apple grants you 50 promotional codes for each version of your app. The code allows the user to download your app from the App Store free. Each code is unique, so be sure to keep track of your codes and who you sent each code to. Also a code is only valid for 4 weeks, and only valid in the US iTunes store. Rather than requesting all 50 codes at once, just request 5 or 10 at a time - however many you need for your immediate promotions.
Promo codes can be requested in iTunes Connect.
A press release may get your app noticed by traditional media - newspapers, magazines, TV shows. Search Google for tips on writing a press release. If you plan to target media in your local area, be sure to emphasize that you're a local iPhone developer; local media likes local stories.
Should you pay for advertising? If you have a quality app, and you can afford to run ads, then the answer is yes. Targeted advertising can bring in buyers. If you can make enough sales to get into the top 100 of your app's category, the payoff can last long after the ad ends.
Web Ad Networks
Many web visitors who see your ad may not even have an iPhone... but some will, so this can be a good strategy if you choose the right site. Look for sites whose audience is a good match for your app's features. For example, a kid's game probably isn't a good app to advertise on a gaming site that features mainly shoot-em-up games.Here are a few suggestions:
- Facebook. While Facebook runs general ads across the entire site, some individual Facebook apps offer their own advertising. Look for Facebook apps that match the theme of your app, and contact the developer to see if they offer advertising.
- iPhone App Review Sites. Some of the same sites mentioned above also offer advertising.
- Daring Fireball is a popular Apple-targeted weblog by John Gruber. He offers weekly sponsorship of the site.
iPhone-Specific Ad networksThese ad networks run ads directly on the iPhone itself, embedded in other apps.
Your Own Users
Once you've got several apps in the store, you should consider marketing to your existing users. You could do this with a mailing list, but a better way would be an in-app newsline or ad that'd displayed to your users when they launch your app. Here's a blog post about using a Newsline to communicate with users.