oh dear.
firstly, your website is on flash. google doesn't like flash. you'll never be anywhere near the front page for any keywords you want, other than your domain name.
you could try adwords, but you're in a competitive industry. you'll be paying lots for clicks.
Try creating a fan page or group page in Facebook and by tagging people you can increase your web presence.
er, no. businesses like yours dont really have a place on facebook. twitter, yes. get a twitter account, start following other graphic designers, design magazines, design websites, etc etc.
Base in my experience in twitter I make a blog in my profile and keep following people its a lot of help to increase a traffic in google.
it won't give you an increase in traffic, but may bring in leads by direct message, etc.
yellow pages - yeah, i think businesses would look at the yellow pages book if they had one when looking for a graphic design company. don't pay too much though.
get on your feet and on the phone. find SMALL local shops/businesses/groups etc that have really bad logos, flyers, whatever and ask if you can design something for them for free, in return for a link on their site, or ask them to pay for money.
don't bother going for businesses who employ more than 5+ people.
easy.