Journalist in big blog or newspaper cannot be reached directly (I think they should receive hundred of mails everyday!). So you need to have a nice app and make some noise and perhaps they will hear about it. I was very lucky for my first app (check the previous post on my blog), but for the second it was easier because people knew about my apps already (it was through Children's Technology Review that I've got an article for Word Wizard)
For the App Store, it is still a mystery but of course you need a great app and with great artwork (I noticed that all the featured app have georgous artwork).