Artists like Weird Al get permission from the original artists, they also don't use any original material, typically. For what it's worth.
Although they aren't legally required to. Al does it as a courtesy. He specifically gets permission from the artist now, because when he did Amish Paradise he'd received an okay from Coolio's label, but later learned Coolio himself was upset about the parody.