Matt Cutts [Google God] has given strong hints that participating in controversial programs like ReviewMe or PayPerPost, that pay bloggers for writing about advertiser's product or services, may jeopardize the search engine rankings of your blog. This also applies to websites selling paid text links on their pages.

Speaking to Mike McDonald, Matt made the following comments on paid text links and paid blog posts:
You want my links for traffic.. totally fine..just don't make it so they affect search engines..so that's why we say use nofollow..or use a redirect which is through robots.txt
Now while some bloggers do write disclaimers [like "This is a paid review" or "Sponsored Links"], Matt has suggested using a machine readable disclosure like a rel=nofollow link.

When Googlebots reads the attribute (rel="nofollow") on hyperlinks, the external linking website won't receive any credit in Google search results or the PageRank.

For instance, the consider the following two cases:

Case A: <a href="www.buy-viagra.com/">Cheap Viagra</a>

Case B: <a href="www.free-viagra.com/" rel="nofollow">Free Viagra</a>

If I have an external link like Case A on my webpage, I am directly helping that [spam] site in Google search rankings [something which Google hates and may penalize my site itself for this practice]

In Case B, search engines will completely ignore the external link [that's the way Google wants you to write advertised links]

Matt shared these views during an interview with WebProNews at the Pubcon conference in Las Vegas. Download full Matt Cutts interview in either MOV or WMV format.

Reminds me of a slightly old article by Amit Varma where he refers to "paid blogging" as deception - "Readers will invariably value the honest blogger more than the plug maestro, and soon the plug maestro will lose his readers."

Interestingly, both Google and Text-Link-Ads are among the main sponsors of the WebmasterWorld Pubcon 2006.

Update: Advertiser links mentioned in Google Adsense, BlogAds, YPN Ads, etc are not visible to search engine bots since they are written using Javascript and are there not parsed by search engines.