how much money do you have to spend? How many users are you trying to get? What is the right demographic (age range, interest etc)?
If it is fun, you might want to try to get hooked into universities. Pick one and just try to get some penetration. University students are single, have time and are more willing to experiment.
Your best bet is going through referrals. But if you can make a funny video on youtube you might be able to get traffic. My sisters friend created a music video for the nohate campaign and they got 30,000 views in a day because they had all the dancers, production people etc to tweet, facebook and share it.