The only thing that really makes a difference in organic SEO matters these days is quality content and links to your site (from other good sites i.e. not mass-ad sites).
I don't know what your business is going to be about but you should think about how to get generating useful content for your users, in a broader sense than only the services that you provide.
For example, if I had a site offering phone unlock services, I might start writing a wiki or knowledge base about how it works and why carriers block phones in the first place - in simple words. Something that is useful to your potential customer both in general knowledge and in the scope of your business.
Another good thing is publishing papers and stuff related to what you or your development team is doing. A lot of big web agencies tend to develop some internal library and later open-source them; then they write a blog about updates, ways it works and how it's useful, etc.
If your content is interesting and useful, then people that have directly or indirectly worked with your company's products will almost certainly start mentioning and linking the reads in blogs, facebook, twitter, you name it. That's the best external SEO you get.
Apart from that, good internal SEO techniques are also important. Make sure all your pages are accessible to the google bot (at least the ones you want google to crawl), include good keyword headers and decent titles. Read the google webmaster blog to learn how to make your content semantic and how to write smart (include the most important keywords in your text, without bloating).
Paid advertising still renders traffic, but it's your job to make that traffic stick and make people come back to your site and make it attractive to new visitors.
PS: Don't hire SEO experts unless you need some very specific advice from them (e.g. how to make shebang style URLs accessible to the google bot). In my experience, even if they're not a scam as per dictionary; everything they know you can find on the internet by yourself.
EDIT
Regarding your question in the comment; think like this:
- Q: What topic do you want google to associate your content with?
- A: Android and iPhone Applications. Facebook Applications.
- Q: Who talks about that topic on the internet?
- A: Other developers. Mobile-devoted communities.
- Q: What's useful content for other app developers?
- A: Tipps and tricks, experiences (both positive and negative), code snippets.
- Q: What's useful content for mobile communities?
- A: Updates, new app features, releases.
A good start would be to set up a categorized blog, on Wordpress or some other well-known blogging system (they have good integrated SEO facilities). Then think of your first project (or some recent one if you already completed some) and share your thoughts and experiences. It doesn't have to be an endless read, 2 or 3 paragraphs is already enough.
Suppose one of your iphone apps got turned down at the apple store for design issues (pretty common thing). What was the reason? How did you feel about it? What steps did you take to solve it? How did you deal with your client's deadline? Make sure to include the e-mail you got from apple somewhere so people that get something similar can google it and find a solution on your site.
