I own a domain/web hosting site and I include advertising for both on the same postcard that I snail mail to new business owners -my osclass site is a local service ads listings for small services/businesses.
I've just started so I really haven't done much advertising yet. I plan to use Facebook a lot. I think the hardest part is branding and getting people to remember your site when they need to list something or search for something they need.
Something I noticed that sites like Twitter and Facebook did a lot of when they were just starting out was to write articles on ways to use their sites. For example, "10 Ways to Profit from Twitter". They would post these seemingly helpful articles on other social sites. I'll be doing something similar to this.
BTW, I've started a subreddit about guerilla marketing for small businesses: http://www.reddit.com/r/gmarketing/