What is that Follow, No Follow thing about ?

IamPower almost got it right.

The no-follow tag was introduced as a way to make spamming sites for backlinks less attractive. It meant that, while the spider would follow and index the link, none of the PR 'juice' would flow to the linked site. Without the link juice, many link spammers would consider the site a waste of time.

Edit: No-follow was also a tool for conserving link juice within your own site. For example, you probably don't care what PR your privacy policy page has. So you would mark links to your PP as 'no-follow'.

There is no such thing as a 'do-follow'. Some people will put a tag inthat says rel=dofollow, but it's null content. It doesn't mean anything.

There is only no-follow and 'not no-follow'.

As for paid links, if that statement was universal, Google would ban any site that used Adwords.

What Google frowns on is buying links for the sole purpose of manipulating search results. The same way they frown on blog spamming, keyword stuffing and any other tactic whose sole reason is to manipulate rankings.

Muddying the water even more, there's a difference between a paid link and paying a service to create links. A paid link would be something like you'd get from TextLinkAds.com. Through the service, you pay a webmaster to put your link on his/her page. Put the link on a page relevant to your site, like a link on a weight loss page to your supplements site, and even then you're likely fine. Put the same link on a sports site or blog, and it will likely be seen as manipulative.