i think you have to advertise on sites which are related to domains and websites. for example alexa.com (you can advertise on this site from adbrite.com)
then whois.sc and others you can find.
forums is a good place. include a link on your signature.
here is a list of some forums
http://forums.digitalpoint.com/showthread.php?t=402803