It depends what your website is all about.
But start with the basics:
1. Make sure your onsite SEO is done correctly.
2. Submit it to search engines.
3. Submit your site to directories under the right category.
4. Build backlinks
5. Create a Facebook Page and Twitter account that is related to your site.
6. Post updates on your Facebook and Twitter regularly.
7. Post new content on your website regularly.
There's much more that you can do...
Before you promote you must produce a site that lends itself to good search engine results. While the technical side may not seem important to the marketing effort, you will soon discover that weak coding will kill a site as quickly as anything.
So you need to make sure to follow best practices for coding that makes SEO easier.
Before you start promoting your website make sure everything is working, try to find bugs, errors. Send it to a friend to check it. (forums, etc)
Make sure your website is eye catching, look on: http://www.webpagesthatsuck.com/
You can use PPC programs like Adwords to promote your site.
There are many ways to promote your site but you should promote it by social bookmarking because nowadays there are lots of users on social sites and its easy to drive them on your site.
Since the other folks have covered the basics of SEO, error checking, and other website aspects.
Other promotional means would also include providing unique content (that isn't directly similar to other content). Each page must contain a title tag, as a SEO standard. You may also consider getting the site reviewed to rate your SEO score.
Here is a website that does a good basic scan to rate one's SEO. http://chkme.com/