IMO, the best, biggest and free means of advertisement, especially for web design is the internet.
Establish a homepage, a name, a brand, something people will remember as I have done.
Think about your target market. Whos gunna bother reading through a phone book to find web designs when its based around the internet and its far easier to use the internet to find people and sample their works.
Approaching companies - Go in and see them. Get a portfolio and show them your designs. Get a good price range in focus - you want to make a bit of money, but don't want to turn customers away by being too pricey. Write letters and send emails too.
Hope that helps.
btw, I'm off to Scotland to fit and wire new drives on a pipe laying ship. 2 weeks of 12 hour days