Yes a press release is you single best tool. PRMAC works pretty well. Do some searching and emulate a well written press release. Of course you will need a web site for the app if you don't already have one. Otherwise the
PR is kind of a waste. It's a good idea to make a You Tube video and embed that in the web page if you can.
Twitter works okay but you will need to start by following people that would be interested in following you. Then you will need to make regular interesting tweets. It takes some time to get built up. What you are trying to achieve are re-tweets by your followers. This is how you create a publicity snowball on twitter.
