For the US see the FTC guidance:
http://www.scribd.com/doc/20635261/FTC-Guides-Concerning-the...
(the FTC has bought prosecutions on this topic recently)
It's also illegal in the UK and presumably a lot of Europe.
You can't make an ad look like an legitimate endorsement, it's as simple as that. In this case the small "sponsored placement" text could easily be taken to be about the following ad which looks like an ad.
If you're just providing links without specific endorsement it's probably fine.
Here's an easier read analysis of the FTC guidelines by the Washington Post:
http://www.washingtonpost.com/wp-dyn/content/article/2009/10...
It's how Dmitry Sklyarov was prosecuted even though his actions were perfectly legal where he performed them in Russia. More recently foreign nationals involved in operating non-american gambling websites have been arrested while in transit through US territory for violating US anti-gambling law.