[kmoser]

OP didn't mention anything about starting from nothing. In any case, even with the newest company, somebody must have contacts: former co-workers, friends, colleagues, peers, etc.

In any case, sales/marketing/advertising is manifold. Have a website with a good explanation of your services and examples of projects you've worked on. (No past projects? Create some, even if just demos/proofs-of-concept.) Make it easy for visitors to join your mailing list for updates (maybe offer them a free whitepaper for joining). Find out where potential customers hang out (whether online or meatspace) and hang out there with them. Ask questions. Discover their pain points and address them. Look for sites that list contracts (yes, there are a bunch) and comb through them carefully and frequently. Don't try to be all things to all people, i.e. focus on customers and projects that can use your strengths. Create a free product and release it to get customers, then try to upsell them on extra features.

Knowing what type of software you specialize in would make it easier to give more specific suggestions. Government contracts are way different from websites for mom-and-pop shops which are themselves way different from embedded systems. Each of those spaces has their own challenges and quirks.