From what I understand, link building, in the semi-legitimate form at least, is contacting bloggers and journalists and saying "Hey, you might really like product X, here's a 30 day trial", sending out press releases, making sure you're in the legitimate directories like yell.com in the UK, etc.
The illegitimate end of is is using hacked forums, wordpress blogs, etc, to post links with exactly the keywords you want to rank for.
And from experience, I can tell you that most "link building" is the spammy type. On a good day, it'll merely be sending out a ton of "link exchange" request emails (a practice which Google also frowns upon, btw).
The illegitimate end of is is using hacked forums, wordpress blogs, etc, to post links with exactly the keywords you want to rank for.