Virtually any song by The Leningrad Cowboys would have to count.
First Kiss by They Might Be Giants.
Spacehog by Spacehog.
Someone else mentioned Planet of Sound by The Pixies. Many songs on the album Trompe le Monde have science fiction overtones, usually dealing with the planet Mars.Lovely Day is my favorite.
Almost anything by Korean singer Lee Jung-Hyun, whose first album was titled “Let’s Go To My Planet”.
The Dread Zeppelin version of Kashmir, where the band gets abducted by aliens.
Just remembered another one The Moon is a Harsh Mistress by Judy Collins.
Is this song based on the Heilein book? I don’t think I’ve ever heard it before.
Per your request andyman :
the song is on the Judith album if I recall and I always thought so, especially in light of the last line :
The Moon is a Harsh Mistress, it’s hard to call your home.
Cool! Thanks! 
Blue Oyster cult * Veteran of the Psychic Wars Vengance: The Pact, Heavy Metal: The Black and Silver*
Deep Purple Space Truckin’
Clutch Escape From the Planet of the Apes
And if Led Zep’s Ramble On gets in so does
Uriah Heap’s The Wizard Great tune about meeting Merlin
Also Moxy Fruvous * You will go to the Moon* Gotta love those crazy Canucks:)
Not surprisingly, Rush has a shitload of sci-fi songs. 2112 and The Body Electric(That title always makes me think of a certain song from Fame) have been covered, but they also did Cygnus X-1, Book One: The Voyage, Natural Science, Digital Man, Vital Signs, Countdown (About the liftoff of the shuttle…close enough to sci-fi for me), Red Tide (Sorta), and The Twilight Zone.
Hell, yes! And I’ve always loved it more than the source song by David Bowie, too!
Also, Doctor Who, by The Timelords (Formerly KLF. Uh huh, uh huh uh huh.), and Flash Gordon by Queen.
Well, the entire album – Kilroy was Here – was an SF allegory for the fight against the forces of repression and censorship.
Too bad Dennis deYoung imploded the band with his overblown theatrical notions about it…
– Bob
Don’t forget “Journey of the Sorceror”, the theme music to The Hitchhiker’s Guide to the Galaxy.
(Okay, okay, that’s a banjo. But it’s close.)
– Bob
No-one has yet mentioned “Blows Against the Empire” by Jefferson Starship, Grateful Dead, et. al. Also, “Karn Evil 9” by Emerson, Lake and Palmer comes to mind. Maybe “Tarkus” as well, but I never could get enough of the lyrics to figure what that one was about.
You want freaky, sci-fi stuff? How about…
“Breathing” - Nuclear fallout as reported from the point of view of a fetus.
“Hello, Earth” - Astronaut looks down, “watching storms start to form over America,” feeling helpless she can’t warn the fishermen and other unsuspecting earthbound folks to get out of the water.
“Rocket’s Tail” - Mostly Kate singing a capella (sp?) while the Trio Bulgarka scat sing in the background. Song about a person who finds they can fly like a rocket with JUST the right “size five boots” and other articles of clothing.
“Rocket Man” - Imagin this Elton John classic done Calypso style. Can be found on “Two Rooms.”
And one non-Kate tune - this one is by a filk group called “The Firm” (no, not THE The Firm), called “Star Trekkin.”
“Staaaaaaaaaar Trekkin across the universe,
Only going forward 'cuz we can’t find reverse.”
Live Long,
Patty
I just found this whole web page crammed with discussion of a great many science fiction songs.
http://www.textfiles.com/sf/sfmusic.txt
sample:
Let’s flip the premise around. Name science fiction stories about rock-‘n’-roll!
Two come to my mind offhand:
The Armageddon Rag by George R. R. Martin. A novel about a rock-‘n’-roll band (The Nazgûl) that was inspired by Tolkien, and gets mixed up in all kinds of occult weirdness, murder, mayhem, and ritual human sacrifice. Lyrics by William Butler Yeats (“What Rough Beast”).
“With a Little Help from Her Friends” by Michael Bishop. A short story about a geriatric Beatles reunion in the year 2013. Ringo returns from the Moon Colony to participate. For John, they substitute a computer synthesized hologram that can do spontaneous wisecracks.
There must be more rock-‘n’-roll science fiction stories you guys can think of.
…a song by Tom Leher called “We’ll All Go Together When We go” about a nuclear holocaust?
And there’s a song on the Dr. Demento 30th anniversary album about a guy who meets up with an alien in a truck stop, but I can’t remeber the name or who did.
OH! And Lenord Nimoy (more-or-less) sang on a song called “Bilbo Biggins.”
AND I’m downloading this entire thread to give me ideas for my radio show. Ta-ta!
Patty
Martian Boogie, by Brownsville Station. (The band is probably better known for “Smokin’ in the Boys’ Room”.)
Worse. He did an entire album of SF/Fantasy songs, of which that was merely one.
I think Shatner, in the middle of that train wreck that he called a singing career, did a similar “theme” album, too.
– Bob
Speaking of post-nuclear-holocaust songs, there’s also Every Day Is Like Sunday by Morrissey (also covered by Natalie Merchant), in which our narrator finds himself “in a coastal town that they forgot to bomb,” where “a strange dust lands on your hands and on your face.”
Well, I know of at least one decent fantasy novel about rock and roll. It’s Gael Baudino’s Gossamer Axe, which is about the Celts, faeries, lesbians, and 1980s heavy metal. Oh yeah.
Actually, I think this qualifies for one reason: The artist says so. If you read the liner notes to “Songs in the Attic,” Billy says something to the extent of “more science fiction than reality now.”
Most of the album, “Fantastic Planet” by Failure.
Including “Another Space Song”, “Heliotropic”, and “Daylight”. One of the best rock albums in the last decade that nobody really heard.
They’re getting closer to this every day: The John Lennon Artifical Intelligence Project.