This happens to me all the time.
Why is it never a song I know ALL the words to? For that matter, why can't it only be songs I like?
Some highlights:
Kylie Minogue- Can't Get You Out of My Head (for about 60 miles of an 80 mile ride)
Fatboy Slim- Rockafella Skank- I actually like this song. Good tempo for hammering or climbing but it'll drive you insane
John Denver- Calypso- This one pops up from time to time. Usually when I'm out doing something long and slow, like climbing mountains.
The Theme From iCarly- My daughter loves this show. That's a double whammy because it gets stuck in my head and it's a kid's show
Anything by Sigue Sigue Sputnik. Fortunately, I'm one of three people in the entire world that actually bought any of their CD's so it's not that common.
Scotland the Brave. We had a song that we had to sing regularly in Officer Candidate School set to Scotland the Brave. Now it's there forever. And I sing it to myself all the time.
One of the things that helps is once an earworm starts cropping up regularly, it goes on my MP3 player. That way, when it starts, I can listen to the song and make it go away.
re-cur-sion ri'-ker-shen n: see recursion