Here's what I did to promote beets (http://beets.radbox.org) over a long period of time (3ish years) before it became "popular":

- Post to domain-specific forums where I thought people would be interested. That includes stuff like /r/python on and /r/music in my case, as well as the user forums for music-streaming systems.

- Build community. IRC, mailing lists, close collaborations on GitHub. Encourage people to become GitHub collaborators early to solidify their commitment to the project.

- Keep trying to delight the users I have. Other people's endorsements on Twitter, HN, etc. consistently work better than my own.

- Screencast. On YouTube so it's easily shareable.

- Patience. Relentlessly make the project better. This is far away the best thing you can do; over the months and years, people will notice.