I’m not sure if the word ‘medieval’ is right to describe what I’m thinking here, but can anyone recommend some songs with themes like knights, princesses, castles, etc? I’m thinking sort of along the lines of All Along The Watchtower. Viva La Vida (song) also has the sort of imagery I’m trying to describe.
How about “Knights in White Satin”?
I only recently found out that isn’t how it’s spelled.
A couple in an Arthurian mood:
Crosby, Stills & Nash: “Guinevere”
Moody Blues: “Are You Sitting Comfortably”
Dancing With The Moonlit Knight by Genesis is the first thing I thought of
also Emerald by Thin Lizzy
and the classics by Queen, Seven Seas of Rhye and Ogre Battle(excellent quality btw–LOVE that guitar). I know Queen has some more…
Oh, and I imagine basically every Opeth song is set in a medieval setting, but it’s not like you’re gonna hear the lyrics without looking em up anyway.
If folk songs are allowed, then we’re opening up a whole new can of wyrms, but I’ll kick off with UK folkies Pentangle performing Hunting Song (warning: link is a YouTube video), featuring the astonishing vocals of Jacqui McShee in her prime.
Gallow’s Pole by Zeppelin.
Medieval justice.
Led Zeppelin’s Battle of Evermore
Neil Young’s After the Gold Rush
Jethro Tull- the entire Songs from the Woods album, also much if not all of the Broadsword and the Beast album
The Mummers Song and most anything by Loreena McKennitt
Good answers so far. I really like The Mummer’s Dance and Fortress Around Your Heart.
A few more: Rainbow had quite a few songs with this type of theme on their first three albums: Rainbow Rising, Ritchie Blackmore’s Rainbow, and I think the third album is called Long Live Rock and Roll. There are too many songs to list, but some of the standouts are Sixteenth Century Greensleeves, Kill the King, and Stargazer. Also, there is Ritchie Blackmore’s folk band, Blackmore’s Night. [STRIKE]Pretty much[/STRIKE] EVERY song is in that theme.
Rush has a few songs like this on their early albums. Check out the album A Farewell to Kings. It’s a great album, and most of the songs have a sort of midievel feel to them…except Cygnus X-1, which is about a voyage into a black hole. 
Pretty much anything by Steeleye Span.
The good Friar already mentioned Jethrol Tull, but I would have to add Thick As A Brick. Altough the imagery is certainly medieval, the subject matter is not.
No one has mentioned Jethro Tull—practically everything from Songs from the Wood has medieval imagery and a medieval feel to it.
By “no one”, I assume you mean “two people”.
Robert Earl Keen’s “Christabel” manages to be both medieval and country. Bizarre, but good.
Fairport Convention - a particularly good example being the (shivers-up-the-spine thanks to Sandy Denny’s extraordinary voice and phrasing) traditional ballad Matty Groves.
Also in the folk realm, Jack Hardy writes a lot of songs that have that Child Ballad feel to them, even though they’re modern. The Knight’s Dream fits your requirements.
Archie Fisher’s “The Witch of the West Mer Lands” (also covered by Stan Rogers) is another modern song with a very old feel to it.
The Smiths - “Bigmouth Strikes Again” references Joan of Arc getting burned at the stake.
Although the song probably has its roots in the Middle Ages, I think Led Zeppelin’s version of it has more of a feel for the 17th and early 18th century.
As for other songs with medieval imagery, there’s “John Barleycorn” which was done by Traffic, Fairport Convention, and many others. It’s another traditional song with roots in the Middle Ages (if not earlier).
Quite a few by Queen
Great King Rat
Liar
Seven Seas of Rhye
White Queen
Ogre Battle
The Fairy Feller’s Master Stroke
The March of the Black Queen
Lily of the Valley
The Prophet’s Song
Bohemian Rhapsody
Speaking of Genesis, there’s also “Timetable” from Foxtrot:
But the song is really about how even the grandest times fade and go away.