My Mobile App is for Business Travelers, Tourists & Locals.
If you're asking about how to *start* spreading the word, my fear for you is that you haven't done sufficient customer development to validate the need for your app and inform your core product thesis. Failure to do so will almost always end-up in product failure.
If this is the case, you might want to slow down on your product building process and refocus on customer development. Building and launching a mobile app that achieves critical mass is one of the hardest challenges one can take-on.
Happy to talk to you in a brief call to outline the customer development process.
You need to start getting into conversations with people who are likely to be potential users of the app. Finding related Twitter chats, for example, and getting involved in those chats, asking and answering questions, is a great way to build community and buzz before the product is launched.
This also will help you in your development, as things will come up that will make sense for you to include or exclude from your app, and you will find a great community of beta users as well.
Let me know if you have any further questions or need assistance in this - social community development is a crucial part of any business now, and I speak on the topic often at conferences.
Get involved with your audience. If it is an app about the restaurant business, start talking to local dining establishments and see how you can work together to promote.
Another great tool (depending on where you are located) is using meetup.com to meet with like minded individuals to network on topics of discussion.
Wherever your mobile app is supposed to live (in the hands of smart phone users), go there and engage with those potential users. They will probably be excited to share with you their thoughts on the App.
This all depends on your budget.
But fundamentally... you have two options:
1) Buy media
Using AdMob or some other ad network provider
2) Generate buzz
These can include things like building a website for your app with some basic SEO running on it and perhaps a small media buy (budget restricted) using adwords
Then, contact app review sites - there are loads of them
Facilitate a JV partnership with other app owners in your niche / vertical.
Would suggest avoiding doing press releases - they just don't work very well.
There is a 3rd option, but sounds like you don't have a budget to work with and that is by working with an app marketing agency (e.g. app promo)
Good luck :)
The first step is to create a landing page and a blog section.
Any PR/communication/sharing you do should link back to the blogpost on your own domain.
Also, make sure to capture potential early adopters.
Post regular updates regarding your development (if you have a well-defined roadmap) and engage user feedback on specific forums.
If you need more details it strongly depend son your product/target.