dnooman, my chem teacher just called those the “BrINClHOF elements” pronounced like… Brinkle Hoff? Worked well enough for me.
The excellent band Models had a song called ‘The truth about Scientists’, which recited the first 10 or so elements - that how I first learnt as a kid.
Then I used something very similar to that used by MalFrog. Through the transition elements I still think of ‘cask tiv croman faeco nick a coppers ink gauge arse’. --> Ca Sc Ti V Cr Mn Fe Co Ni Cu Zn Ga Ge As
When I was five I had a record of “space songs” (“Meet Space Pilot Jones/His body, it looks like a barrel…”, about space suits; “Is it raining in Paris?/Will it snow in New York…”, about weather satellites). One of the songs went:
Mercury, Venus
Earth and Mars
Jupiter, Saturn, Uranus
Neptune and Pluto!
The wandering stars!
My sister, who is rather older than I am, hated the record because I played it so much. (You know how small children can be obsessive with their entertainment.) But she admits that The Wandering Stars, which was without her permission pounded into her head, helped her on a science test in school. 
It isn’t a song, and doesn’t have anything to do with the periodic table, but my favorite mnemonic device was a short sentence for biology: Keep penises covered or fuck and get STDs. Kingdom, phylum… well, you know the rest. 
I heard that once and have never been able to forget it. Plus, you know, it is good advice…
I heard it as "King Philip Came Over From Germany Smiling.
This was my first thought. Songs and such certainly CAN be helpful in memorization and School House Rock did it for an entire generation of americans.
If you ever have the opportunity to pick up the DVD do so. Trust me on this one. We’re using it for the four-year-old right now.
I learned the planets as “M VEM J SUN P” and it has stuck.
Mary’s Violet Eyes Make John Stay Up Late Nights, Period
Oh, and we were taught an almost-song in high school religion class (Catholic school) to remember the Epistles in the New Testament:
Ro co co Gal Eph phi col thess thess tim tim ti phil heb
Romans, 1 Corinthians, 2 Corinthians, Galatians, Ephesians, Phillipians, Colossians, 1 Thessalonians, 2 Thessalonians, 1 Timothy, 2 Timothy, Titus, Philemon, Hebrews
On the other hand, I can’t remember the non-Pauline epistles for shit…
And who could forget the lovesick astronomer’s lament for memorizing the (unalphabetic) sequence of stellar classes?
My cousin’s second grade class learned “Fifty Nifty United States.”
This is a memory trip through my elementary school days. I still say, “I before e, except after c, or in words with an “ay” as in neighbor and weigh.” I still say please excuse my dear Aunt Sally to remember my order of operations- parenthesis, exponents, multiplication, division, addition, subtraction. I still say “Thirty days hath September.”
And not a song or a rhyme, but did anyone learn how to remember the multiplication rules for the number nine on their fingers? I didn’t learn that one as a kid, but, my, that would have made my third grade days easier.
Don’t forget the ultimate and earliest mnemonic device for English speakers: the alphabet song.
I didn’t know about the nine trick until calculus. Not that I ever needed it, but I feel there’s this whole subculture I’m missing out on. 
I, too, had to learn “Fifty Nifty United States” in 5th grade.
I remember in Sunday school we had to learn songs that listed the books of the Bible. From the Old Testament song, I can remember Genesis, Exodus, Leviticus, Numbers, Deuteronomy, Joshua, and Judges. From the New Testament song, I can remember Matthew, Mark, Luke, John, Acts, Romans, 1 Corinthians, 2 Corinthians, Galatians, and Ephesians. That came in handy for Scholastic Bowl a couple of times.
There’s a semi-dirty one to remember something biological (the Krebs Cycle?) that involves Caesar and orgies–can’t remember that one, cause I never paid much attention in bio. There’s also a dirty one to remember the resistor color codes, but I never learned it. Maybe someone will come along and know those.
Here’s one version: “Bad Boys Rape Our Young Girls But Violet Gives Willingly”. Incidentally, the same color code is used to mark some capacitors and inductors too.
For lots and lots of mnemonic songs (and also bunches of useless but pleasantly arcane songs), try Greg’s science song links.
I got mine from ‘Have Space Suit Will Travel’ by Heinlein
Mother Very Thoughtfully Made A Jelly Sandwich Under No Protest.
Note that us cool Heinlein fans work in the Asteroids and call Earth ‘Terra’.