Bilbosax What we did running as a startup, was befriending media. Although it might seem like a difficult thing, you will be amazed on how "hungry" for news they are. So at first we started contacting them directly with a small brief over milestones "We are tourismart, we do that , we won X award." After a while they started checking with us for news.
A press release in most cases it is just a 1 pager announcing something like a new major release, awards, big milestones.
As 2dguy said, it is all about marketing, so after releasing your apps you should be focusing most of your power to marketing and promoting them.