Well, back in the day, it was stuff like setting up blogs that linked back to your site, making somewhat-relevant blog comments elsewhere, submissions to directories, issuing 'press releases', making forum posts (especially with signature links), making somewhat-relevant contributions to wikis, 'contributing' to bookmarking sites like del.icio.us, providing somewhat-relevant answers on Yahoo! Answers, you get the idea. If you could stick a link in it, you stuck a link in it.

For all I know any or all of these tactics could currently be the search engine kiss of death - so don't do any of them without doing your research first. Search engines have probably gotten a wee bit smarter.

The other, more ethical way to do it is to produce great content (reviews, tutorials, photo shoots, etc.) that people might actually want to link to of their own free will, but this is time-consuming and hard to scale up.