Submit to HN, reddit, digg, etc.
Contact relevant and/or popular blogs/news outlets with non-form emails as to how and why they should write about your site. Getting on Lifehacker was a huge boost for one of my side projects.
If you can afford it buy the keywords on google, yahoo, msn that are extremely relevant.
Post to various web application directories(this was probably the least effective use of time)