It depends a lot of the topic of your company, but in general, you can do different things:

Contact with bloggers and journalist once your project is on air.

Also start writing a blog about your company and try to create relevant content, it is really amazing how a blog can help you at the beginning (seo, traffic, value).

Algo create a Facebook Page and invite (spam) all your friends asking them for help to spread the word. Do not underestimate your social graph, it could be really valuable.

Create a Twitter account and start sharing interesting content related to your project.