I've used twitter and my blog (geomblog.blogspot.com) with some degree of success. I'll probably also request specific bloggers (the complexity blog, Dick Lipton etc) to advertise it as well.
Update: Here are some specific examples of posts. I've tried to highlight certain posts from the main site that might catch people's eyes: I'll do this semi-regularly from now on.
- Latest news from the unnamed-but-working-on-it theoryCS Q&A site
- cstheory Q&A site now open to the public !