I recently came across a clip of the skit as done on the old Muppet Show in 1977.
But I *swear* that I had heard it earlier, on Seasame Street, and according to this site, I am correct. It was done sone Sesame Street in 1969. And apparently, Jim Hensen did it even before then, when he appeared on the Ed Sullivan show, in 1968!
But the origin of the song? It's even more bizarre than you would think
According to this site it was written by Piero Umiliani, an Italian composer, for a Swedish porn flick titled Svezia: Inferno e Paradiso (in English, "Sweden; Heaven or Hell".