AppStore SEO Tips
As others have pointed out, it's a shame that Apple hasn't made the the App Store's search algorithm more transparent. Getting your app up the rankings is still a black art, and new apps are at a massive disadvantage simply because they haven't been able to experiment with black-magic SEO tactics as much as incumbent apps.
With that said, I still need to get My Minutes up the rankings. This post is a collection of App Store SEO tips I've come across. I've been trying some and will be trying others as I release more updates.
Words in your app name are treated as keywords. Don't waste your 100 characters by duplicating words found in your app name.
Stuff additional keywords into your title, but keep it within reason. If you do manage to show up in search results, a spammy app title isn't going to help.
Include both singular and plural forms for your keywords.You won't show up in a search for shopping lists if you have just the list keyword. (Apparently, since acquiring Chomp, the App Store's search has gotten better about this, so - as with the other tips - take this with a grain of salt and test your changes.)
Phrases don't matter. A search for recipe book will match against recipe,book just fine.
Be careful of using a competitor's app name as a keyword. Apple reviewers may flag the keyword and you lose those characters.
Terms such as "free" and "cheap" are heavily searched. If you are putting out a free app, **include "free" as a keyword.
App reviews are very influential in the App Store, so try to get your users to leave you a review. A helpful tool for this Appirater. The more reviews and the higher your average rating, the more prominent your app will be.
App popularity is a big factor. Competing for ranking in high-traffic searches that are dominated by established and popular apps is probably not a good idea. Try to find niche searches where your app can rank highly.
Keep in mind that none of these are proven to work. It's just collective anecdotal data that has worked for some developers, so it's important that you track whether the changes you're making are actually helping you.