We launched into an audience we knew well, and already worked for. The product is pitched at web designers, as a consultancy the majority of our clients were web design agencies. Our main initial tactic - and something we still do - was to write content that appealed to that audience. Not necessarily anything to do with content management, but anything that might appeal to designers and design agencies and then link back to Perch.
I've experimented quite a bit with BuySellAds (http://buysellads.com/). There are bargains to be had that convert well if you look at the smaller sites, and find those that are well matched to your audience. They might not send through huge amounts of traffic but if they are really well selected then the conversion rate can be better than the expensive high traffic sites.
The surprising success for us in terms of advertising has been sponsoring relevant podcasts. In our case that is podcasts that target web designers. The trick is to sponsor those who actually take the time to talk a bit about the product during the show - rather than just read out your name at the beginning. We've also managed to find podcasts where the hosts use Perch - that's even better!
Mostly it is just working on incremental gains in terms of traffic and visibility. An article here and there, some well placed ads, sponsoring podcasts. None of this causes a crazy rush of traffic but we're in it for the long game, so a steady growth that is sustainable is really more interesting to me.