Give it a good name.
What I think is an important aspect of creating awareness for a project - especially young projects - is how easy it is to search for the given name on, say, Google. In order to get search engines to associate the problem your project is trying to solve, with its name, you need to pick a name that is not already tightly coupled to an existing meme.
I learned this the hard way. I created a project, called in Fabric and implemented it in Python - this combination generally associates very strongly with clothing, and it has made it very difficult to find the project on Google.
The other thing you need to do, is to keep making noise about your project; blog about it, comment about it in discussions that concern the problem it is solving, and submit it to sites like freshmeat, ohloh and the like. You might even write about it on mailing lists and forums that might have a high percentage of possible users, but be careful not to be labeled a spammer when you do that. I think it is safe to do that if the project has a real possibility of being useful to those people and you're being polite and humble about it (you are sort of treaspassing into their yard with a banner).
Lastly, you need to keep the project alive. Keep releasing new versions, keep committing new code and just generally keep the activety level up. You don't have to throw endless hours at it, you just have to keep it afloat. People will look at stuff like when the last release was, but they won't pay as much attention to how much work went into that, or any, release.