See if there are any local papers that cater to businesses. Their advertising rates might be reasonable (less than the major newspapers, anyway), and you can update your ad as often as you want.
Contact and/or join the local chamber of commerce. There are usually functions so you can meet other members, so you can do some networking.
Do your own mailing. Contact a list house to buy a list of businesses in your area and send out letters, brochures, business cards to local companies. You can usually purchase mailing lists on CD or preprinted labels, and you can specify by zip code, business type, etc.
Warning: money suck! I advertised for my graphic design in the Yellow pages and it was a real waste of money, plus there's a year lead time before your ad comes out. Because I live in a college town, the only calls I ever got were from people looking for jobs. I expect the online versions are just as bad, if not worse.
Sales pitch: I do writing and graphic design, if you need some business cards or brochures!
Before you post, read our: 
