It is hard unless get the attention of the Press or Apple. Getting discovered based on just popping up in an App Store search is very difficult. There are many threads like this (I recall) on the old developer forums and I'm sure there are some on these forums. If you do show up in the search results, you have to be in the top 10 of a good popular search query I think to get a good amount of daily downloads. Almost nobody scrolls beyond 10 and you can be better than your competitor but if you are further down the page it won't matter.
I've experimented with paid ads (Twitter ads) and I didn't find them to work well. I of course don't have a lot of money so I couldn't pour thousands of dollars into it. You can have an ad campaign drain hundreds of dollars within an hour (or space it out throughout the week if you want) based on clicks and what not and if you are only selling your app for 99 cents, you really need some deep pockets to pay for enough advertising to tell if it will actually work.
You are not likely going to get an answer here that will be helpful. Basically the answers will likely be one of the following:
1) Make a website for your app. Maybe a few youtube videos.
2) Contact the press and blog sites and hope they answer.
3) Buy ads.
4) Experiment with different keywords, though generally any advice related to keywords is always vague and I honestly do not believe that there are many people (if any people) who know how keywords work who don't work for Apple. They just get lucky and say it is because they have good keywords, or they are trying to sell you something (total guess, don't take it too seriously). On the App Store it is especially hard to experiment with keywords because you have to submit a new app update to change your keywords.
5) Take your vitamins and say your prayers.
I've been working on Mac apps lately. I don't know what everyones sales reports look like but I get the sense that you are either first or last on the iOS App Store.
