Make a blog. Seriously, write a blog about why you made a newsletter, what the newsletter will include, and any benefits users will receive from signing up for it. It's a great way to not only promote it, but also create content for the site.