In Campbell v. Acuff-Rose Music Inc. the 'live2 crew' won on their parody of "Pretty Women", because they were making a comment on the original song. While family guy lost "when you wish upon a weinstein" because they merely appropriated the "when you wish upon a star" song to comment America's stereotype of Jews. But they weren't saying anything about the song.

Basically I can parody your work to make a comment on it. I can't appropriate it to parody someone else.

Weird Al gets permission from the artist - but that's mainly a, don't cause trouble, keep the record company happy.

He would still have to pay for the rights to the music owners when the song is used, although the owner of the music rights may well not be the artist. Which is why some songs are performed live but not on the albums - the payment for singing "happy birthday" at a concert is very different from putting out a cd of it.

ps - I am not a lawyer - although my dog has been trained to piss on their BMWs