You should start off with a link building campaign.
1. Link exchanges - Link exchanges can be very effective if done with sites of the same topics or subjects.They are two-way (they link to you and you link back) links. You can email webmasters and request a link exchange with the proper anchor text.
2.Article submission - Submit articles you have written to article directories. Usually they have an author's bio, where you can place your site's URL in it with the appropriate anchor text.
3.Directory Submission - Submit your site to various directories. There are free and paid directories. It would be advisable to submit your directories to free directories(especially DMOZ) and choose which paid directories you would like to submit to.
4.Forum posting - Signatures allow you to place links and anchor text to your site. If you are posting in a forum related to your site( and with a lot of keywords), you can get better results in your rankings from these postings.
5.-Blogging - Nowadays everyone likes to leave comments in blogs. You can do it as well. And add your link with the comment. However remember not to spam blog sites, if you add a comment make sure that comment has something to do with the topic.
Most of the major search engines pay attention to the number of sites linking back to a website and ranks the website accordingly. So more the number of back links, the better for your website.

The off page optimization methods I use are:

1. Press Release Marketing
2. Article Marketing
3. Social Bookmarking
4. Web 2.0 Sites
5. Forum Marketing
6. Blog Commenting

*Keys* Try to get as many anchor text links to different pages on your blog or website

I can go into detail. But that would take a long time.

You've gotten some great techniques already, and I just want to add 1 more - guest blogging. It's a great technique, even if you don't own a blog yourself. Guest blogging gives you a great backlink, and it gets your name/link out in front of very targeted traffic.

But before you do any of these off-page techniques, you need to make sure that your on-page optimization is taken care of. The best off-page strategy in the world won't work as well without a strong on-page foundation.

Off-page optimization (off-page SEO) is what can be done off the pages of a website to maximize its performance in the search engines for target keywords related to the on-page content and keywords in off-page direct-links.Some of the off page optimization activities are:

• Link Building
• Directory Submission
• Article Writing
• Article Submission
• Press Releases

Link building is an off page optimization it includes classified ads, social bookmarking, social networking, site directories, blogging, article submission, blog commenting and forum ads.