Its perfectly legal as long as the person who's buying them owns their own website, your cant do it on sites such as blogger. The only reason people dont do it is because you can get penalised by google for doing it.
Of course it's legal! If someone owns that webspace, they are allowed to do whatever they want with it. However, like many others have said, search engines such as Google frown on paid links. They look mainly for natural links.
What methods does Google emply in order to detect paid link schemes? Are they thorough in cracking down on this practice?