Welcome to the forum, @Dregs.
This issue has been discussed before, so if you search - especially within the Marketing category - you’ll find some ideas.
I think the most recent discussion was here:
How to promote classifieds site?
Among others, you might also want to check out these:
How to promote a Classifieds Website?
http://www.sitepoint.com/community/t/how-to-promote-classified-ad-site/69547/10
http://www.sitepoint.com/community/t/how-to-promote-a-classifieds-website/4321/13