The best advise I could give anyone is to test, test and then do more tests..
There is no magic formula, unfortunately. All you can do is spread your advertising budget around and run test campaigns constantly to see what works for your company and what doesn't. Your first 10 campaigns using Google Adwords might fail and give you no sign ups for example, and then the next one will bring you 10 sign ups in two days just because you changed the wording on your Ad, or your keywords.
First, ask yourself this question.. How much am I willing to spend, or can afford to spend, for ONE client?.. $20, $30, how about $50? For me, if I spend $100 in Adwords and gain 2-3 new clients from it I consider it money well spent. This also has a lot to do with your company's Customer Retention Rate, and client loyalty for your brand. If your customers are happy and stick around, then you should be willing to spend more money in order to gain a quality client.
What do I mean by quality client? I mean "know your market".. Don't advertise somewhere just because it's a cheap place to put a banner there. Advertise is places where the customers YOU WANT, will hang out at (e.g - If you're selling web hosting, don't advertise on a hacker forum...). Also, don't just throw money away just because you have it.. There are many places where you can advertise your company for FREE and gain quality sign ups as well.
Some places I recommend you start with:
1. Hosting Discussion Showcase and Marketplace Forums
2. Web Hosting Talk Forums and WHIR
3. Twitter, Facebook and other social network sites
4. Google Adwords (requires a lot of trial and error, but it DOES work)
5. Local Advertising (signs, flyers, post cards, ect..)
And as always try your best to exceed your customer's expectations and treat them how you would like to be treated if you were in their shoes.. Lets not forget about the most powerful form of advertising: WORD OF MOUTH.