MuppetDude's description is pretty full. Though I think it was actually a Nestrapolitan Opera sequence. The song (with rewritten lyrics) was of course The Habenara from the opera Carmen (hence the name Charmin').MuppetDude said:Make that a black hat and large magenta bowtie.
Charmin' was a live-hand orange AM that resembled Louise Gold and dressed as a Spanish flamenco dancer. She appears in an episode of "Pretty Great Performances" where she sends faxes to her far-away love, then ends up falling in love with sending faxes.
BTW, Count, her love's name is Jose, and was a lavendar live-hand AM with a pink nose, black hair, and lavendar eyelids, and dressed as a matador.
Incidentally, the skit must have been filmed in the early 1990's (cause Louise Gold only puppeteered on Sesame Street during the first half of the 1990s)