This is something I'm trying to learn how to do as well! Things that I'm in the middle of:
- Going to social/entrepreneur mixers and meeting people to talk about my site. The in person aspect of this is also a great way to get feedback on the idea.
- Providing frequent updates through my own contacts on social media.
- Contacting prominent bloggers in related topics about writing a guest blog post.
- If it's fitting, Hacker News!
I would love to hear what other people are doing besides spending a ton of money on ads.