Roy Zimmerman's song "Firing the Surgeon General" established the title phrase as a euphemism for masturbation (by paralleling it to a number of other such euphemisms) to satirize the controversy that resulted in the 1994 dismissal of Surgeon General Joycelyn Elders.
Limp Bizkit's Chocolate Starfish and the Hot Dog Flavored Water. "Chocolate starfish" here being a euphemism for asshole, while "hot dog flavoured water" comes from an in-joke about how Wes Borland saw flavoured water on sale at a truck stop while touring, and jokingly wondered if they also come in meat or hot dog flavour.
When Emilie Autumn performed her song "Misery Loves Company" on a morning news show, she replaced the line "pray for me you fucker, if you fucking dare" with "pray for me you muffin, if you muffin dare".
The song "Mutha'Uckas" and the term Muther'flippin from "Hiphophippotomous Vs. Rhymnocerous"
Played with in the music video for "Laid" by the band James. One line originally goes "But she only comes when she's on top." The version used in the music video replaces "comes" with "sings" - but that part of the video has a close shot of the lead singer, who is obviously singing the original lyric.
Originally composed for the alt.games.nintendo.pokemon.hentai newsgroup, the song "I Wanna Slowpoke Your Cloyster ('Till My Bulbasaur)" introduced the title phrase, as well as "jiggling the Jigglypuff".
"The Fez" by Steely Dan isn't about a hat. It's a (made up?) euphemism for a condom.
But then "Steely Dan" is a euphemism for an erection, so that's hardly surprising.
Steely Dan actually took their name from the nickname for a large metal dildo in Naked Lunch.
Viktor Vaughn's song "Mister Clean" has little to do with cleaning supplies; the title refers to Vik's insistance that his barber "Give me a Mister Clean", or shave his head completely, at the end.
Vik has a lot of strange or unique words or phrases. At one point he reminisces about something that happened "six degrees ago", etc.
The same artist does something similar in his Kind Geedorah persona; Geedorah is a space monster who doesn't truly understand humanity, and his alien perspective is partially represented by some seriously idiosyncratic speech quirks.
In the Meat Loaf song I'd Do Anything For Love (But I Won't Do That), "that" is a reference to a previous line where the singer names a thing he would never do ("forget the way you feel", "stop dreaming of you", etc.) Due in no small part to the complexity of the lyrical construction, it's also assumed by many listeners to be a euphemism for something else, to the point where Meat Loaf says "What is that?" is the most frequent question he's asked by his fans.
"Elektronik Supersonik" by Zlad! includes the lines "I put my port plug in your socket" and "So onto my love rocket, climb."
Rammstein does that kinda often as well. Most notably in Pussy. Blitzkrieg mit dem Fleischgewehr!
A radio edit of Jethro Tull's "Locomotive Breath" removed "balls" and spliced in the word "fun" from the previous verse, resulting in the strange expression "got him by the fun."
Starflyer 59: While their lyrics never use any words worse than "hell", Jason Martin reportedly used (and possibly still uses) euphemisms like "what the eff" and "piece of shin".
Steeleye Span's "Drink Down The Moon" uses "cuckoo's nest" to refer to female genitalia.
Aerosmith songs are full of this. Most notably the famous "Walk This Way" has this line "You ain't seen nothin' 'till you're down on a muffin." Lady Gaga's line in "Poker Face" is probably a Shout-Out to this song.
"Muff" may be dated, but it's not an unusual expression, at least not in 1975.
Insane Clown Posse use the terms "Neden" and "Cotton Candy" over "vagina" or "pussy"; other Psychopathic Records artists have used this term as well: Anybody Killa released a song called "Your Neden's Haunted", loosely about sexually-transmitted disease ala ICP's "Bugz On My Nugz".
"Precious" by Pretenders has "I had my eye on your imperial". It doesn't sound like she means a car. More like a scepter.
A possibly once-common expression, used to give an old-fashioned feel to John Fogerty's "Centerfield": according to Word of God, "Brown-eyed handsome man" is an old-time expression for "African-American". Might also pop up in Van Morrison's "Brown Eyed Girl" and Led Zeppelin's "Good Times Bad Times".
"House of Fun" by Madness is about a teenage boy trying to buy condoms from the chemist, but is too embarrassed to actually say "condoms", so he uses euphemisms that the poor lady behind the counter doesn't understand. When he asks for "party favors, balloons" and "party poppers," she tells him to try the titular joke shop around the corner.
The music of Devo is chock full of strange, obscure euphemisms, an extreme example being their demo song "Goo Goo Itch":
Itchy, itchy goo, there's a pile next to you
Itchy goo, itchy goo and it's turning blue
Itchy goo, itchy goo, itchy goo, goo, goo
It's all I want to do, whammo!
Nobody (apparently even Jerry Casale) is quite sure what "Sloppy (I Saw My Baby Gettin')" is about.
I saw my baby yesterday
She spent her money on a car
It didn't get her very far
So my baby said to me
You know my baby she said sloppy
I think I missed the hole
"Be Stiff", if you can discern the lyrics to begin with, has lines such as "Fruit ooze is wetly lewd, so stay dry in rubber boots," "Cucumbers ripe and rude," "Breathe hard in metal suits," and so forth.
The opening line of "Combine Harvester" by The Wurzels: "I drove my tractor through your haystack last night."
From Autumn to Ashes' "Take Her to the Music Store" was written about a friend who was raped, or "fucked against her own will." The title is based off of an euphemism, "taken to the music store," created among bandmates after a bad experience with a local music store that ripped them off (or rather, fucked the band against their own will).
Eminem's song "Fack". (Warning: the song is very NSFW.) Guess what "fack" is a synonym for.
"Oh God, I wanna facking fack" "No, not 'fuck', I said 'fack'" "F-A-C-K F-A-C-K fack, fack fack facking freak me!"
En Vogue's "Don't Let Go (Love)" seems to be a song about coercing a man to make his relationship with the singer official, curiously urging him to "lose control."
Nicki Minaj's song "Anaconda" is a subversion, in that the verses are quite explicit in their subject matter. But the refrain consists of this line repeated over and over again: "My anaconda don't want none unless you got buns!"
Punk band Vagiant happens to also work for Harmonix, and as such got one of their songs into Guitar Hero II. The song in question is "Fuck the Kells", and had to be heavily edited for the T-rated game (such as replacing nearly all cases of "fuck" with "frack" and renaming the whole song to "FTK"). One memorable change was "You can take this bar, and shove it up your fuckin' ass!" becoming "You can take this car, and fill it up with tons o' gas!" Which... could be construed as wanting you to hit the road, Jack, and get as far away from them as a full tank will take ya.
John Hiatt & Little Village have "Solar Sex Panel". Sort of ecologically correct version of the Bawdy Song.
The Ninja Sex Party song Peppermint Creams is about a knight who really enjoys the princess' "peppermint creams". The chorus reveals (loudly and at length) that he means her breasts and bottom, not that she makes really good York patties.
Blue Man Group has "Shake Your Euphemism", which lists off different terms for "butt". Some of them are normal, like "hind-quarters", "booty", and "buttocks". Others are... very strange, like "your dinner with Andre", "Mothra", and "the place where all the burritos go".
Ann Wilson's "My Thing Is My Own" contains several rather interesting 18th-century euphemisms for sexual matters.
A cunning clockmaker did court me as well And promised me riches if I'd ring his bell So I looked at his clockwork, and said with a shock Your pendulum's far too small for my clock
Bad Lip Reading: Shooting a Russian Unicorn, if the lyrics doesn't already make it clear what the term alludes to.