One method you may want to consider if it fits with your project is to provide easy ways to integrate it with other popular programs or applications. For example, if it's web-based, you may be able to integrate it with Facebook.
Great demos and documentation also are a great way to spread the word, as are tutorials about how to use your project on third-party sites like Smashing Magazine, NetTuts, etc. There are also many script directories like HotScripts that you can submit to.
Also, there is nothing stopping you from submitting press releases to sites like ReadWriteWeb, TechCrunch, AllThingsD and a slew of others that are dedicated to tech coverage. They aren't required to cover you, but if your project is interesting enough, they might mention it. Plus it's free.
Social media is another avenue that you can pursue. If you can, you should add a social bookmarking widget like AddThis on your front page so people can easily bookmark it. You can also submit to those sites yourself. Forums are another type of social media that can be great, if used effectively.
However you promote your project, make sure that you tailor your message for the medium. Just cut-and-pasting posts into forums is spam. Make sure that you look around and see if there is an appropriate place to post and if you're not sure, ask. And if you're sending out press releases, again, tailor it to the individual site or person and contact them the way they want to be contacted.
Also, do everything you can to make it easy for people to find information within your project. Think of what will make things easiest and what will be most helpful for your users. Make it clear what problems your project solves, why, and how. If you can incorporate community in the form of help forums,error tracking, or plugin architecture, do that as well. It may take a little time away from coding, but it will pay off.