Find related sites (best not be competitor sites!) and perhaps contact the webmaster via email for a free link exchange, i.e. you link to his site, he links to your site.
Alternatively, if you have money to spend, you can purchase a link on a webpage. Normally, pages which receive a lot of visitors, or have a high Google pageranking (you can view this with the free Google toolbar, or use one of the many online tools around the web) will cost the most.
Forum signatures are a good starting point. Use anchor text links, such as the ones in my sig. Even though I have 4000 or so posts which have a sig, only a few of them will be of any benefit, not all the links will be indexed. But, it's worth getting as much as you can.
Beware of the sandbox theory however, apparently if you build up a vast number of links for a new website in a short period of time, consequences such as dissappearing from Google search results can occur!