advertising probably the hardest bit when I started my own little business. The place where I seem to get most of my leads is actually Graphic Design Company Services - Web, Print & Advertising . Apart from online directories (also can help in link building) word of mouth can get you a good amount of work, just make sure you get the credit where due.
Wherever potential customers will see :up: to be honest, I would go nuts with advertising. Be confident, get your name out there, eventually people will come and, if a good job is done the flock will follow