Since you seem to be a B2B advertising company yourself, and you need the services of a B2B advertising company, the cheapest thing you could do would be to use your own services. But you have probably thought of that already...
If I can extrapolate from your question, I don't think you are looking to build a brand so much as get web traffic. "Cheap" and "effective" are often at cross purposes. What you really want is "cost effective".
It all starts here. This is a good post about SEO.
You will probably want to stay away from PPC for now as it has a learning curve that can cost some money up front. (Not a learning curve about PPC itself, but a learning curve about which keywords are profitable.) I know, some of you out there are raving PPC fans. But remember, @NewWebStartUp said "cheap".
For less than $50 a month you can distribute to web publishers an unlimited number of articles that establish your credibility as an expert in your field and get you links back to your site. Full disclosure: this is what my company does. See my profile if you want to more info.
You can make some fairly small ad buys at a variety of places. Here is a list of ad brokers you can use.