There's nothing you can do besides making a good app. You'll not be able to pay for advertising. When I published my app, I sent a "press release" to ten iPhone app review blogs. None of them reviewed my app, almost all of them automatically sent me an email after two days telling me to give them $100 so they'd publish the review (yeah right....

).
A great jump of sales (for me: ~1,800%) is being feature in the "New and Noteworthy" category in iTunes. In the one week while I was featured, I sold more copies of my app than in one entire year. I don't believe you can influence being featured, however. I did absolutely nothing and got featured, other people invested great efforts and did not get featured.
Generally, I guess you should just try to make a good app and not concentrate on marketing. If you're not a major developing company, marketing seems mostly pointless to me.