Magma was already mentioned, but there’s also the prog band Ayreon (really a solo project under a band name), whose entire catalog tells a single story.
Oh yeah, and there’s Dream Theater’s “Twelve-step Suite,” which spans five albums, but I’m not sure how well it fits the requirements of the OP, as the songs are more a reflection on Mike Portnoy’s experiences than an actual story.
The musical Annie had two sequels: Annie 2: Miss Hannigan’s Revenge and Annie Warbucks.
I didn’t this want to evolve into “name your favorite concept album,” otherwise the requirements would have been a bit loser. I’m pleased with the number of examples so far though.
This example is exactly what I was looking for. Despite mentioning Queensrÿche in the OP, I stupidly forgot to consider heavier bands. I was unfamiliar with Coheed and Cambria, so I’m very grateful for this mention.
The bitterness of the Final Cut, the Wall, Animals, etc., etc., … 
I wasn’t sure what to think of Pink Floyd. I never thought about Roger’s father as a character. I did think of mentioning the school master from the Wall, since he shows up in three songs there, and then seems to appear on the Final Cut as well.
As an aside, “When the Tigers Broke Free” has actually been included on newer copies of the Final Cut, where it’s included after “One of the Few”. This placement bugs me because it splits up the school master’s lament.
I had completely forgotten about Charlotte.
No. I thought including opera might make it too easy. Plus, I wouldn’t be motivated to go out and seek some of the music mentioned.
I wasn’t aware of this. Then again, my exposure to the movie Annie was less than pleasant. It’s the only movie that I’ve ever seen more than 30 times, and, not so coincidentally, it’s one of my least favorite movies. (The original Star Wars may have surpassed it in viewings recently).
I had always heard that the first couple waves of albums from the Wu Tang Clan (the Wu Tang Clan albums and the individual member’s albums) create a consistent mythology throughout. While I listened and enjoyed many of them, I never really concentrated on the lyrics enough to verify that, but I wanted to throw it out there in case someone else knows more about it.
Gong, with their Radio Gnome Invisible trilogy of LPs. One continuing (if meandering) storyline, compete with characters.
Missed edit window… Be sure to scroll down that Wikipedia article for a detailed description of the Radio Gnome Invisible story.
Also… how could I forget Parliament/Funkadelic and the P-Funk mythology.
I hereby kick myself for not thinking of Zero the Hero, the Octave Doctors, and the Pot Head Pixies myself!
I assume we’re not including characters in concept albums or single compositions with multiple movements (i.e. Rush’s 2112).
Blue Oyster Cult’s Astronomy and Subhuman/Blue Oyster Cult songs from previous albums were both drawn into the mythology of the Imaginos album.
Jethro Tull’s Auqalung character appears in Aqualung, Cross-eyed Mary and is possibly referenced in Strange Avenues (looking like a record cover from 1971 [the year Aqualung was released]). To be fair, the last reference may be more self-referential than a reference to the character.
They’re not exactly my thing, but Insane Clown Posse’s entire discography (at least before the last album) it building up one big mythology, the “Dark Carnival.” I don’t know if specific characters appear across albums, but when I think of bands developing a thematic universe, ICP comes to mind right away.
Ween The Stallion
Jethro Tull has several that qualify. “Jeffrey” shows up on at least 4 albums that I know of. Certain background characters also show up on Passion Play, Aqualung and Thick As A Brick.
Prince By-Tor appears on Rush’s second album, Fly By Night, in By-Tor and the Snow Dog. He appears again on their third album, Caress of Steel, in The Necromancer. In the former he is the bad guy, in the latter, the good guy. Rush has never said which story comes first.
Jane Siberry has three songs, on three different albums: “Map of the World, Pt. 1” on her 1984 album No Borders Here, “Map of the World (Part II)” on her 1985 album The Speckless Sky and “Are We Dancing Now? (Map III)” on her 1995 album Bound by the Beauty. Like most of Jane’s work, it’s hard to definitively state that they are a continuing story, but they seem to meet the criteria of the OP.
Phish has the concept album (never been officially released) that tells the story of Gamehenge and the many characters from that world including the bad guy there named Wilson. Over the years, a bunch of other Gamehange-inspired songs have come out on a few of their studio albums…
Junta: Icculus, Divided Sky
A Picture of Nectar: Llama
Hoist: Axilla, Part 2
There’s also been a bunch of songs that haven’t appeared on any studio release…
McGrupp & the Watchful Hosemasters, Punch You in The Eye, Harpua and Axilla (part 1)
Does the “Fear Trilogy” from Rush count?
They’ve also got the Metropolis storyline. “Metropolis Part 1: The Miracle and the Sleeper” is a track off of the album Images and Words. The story is continued with the band’s concept album Metropolis Part 2: Scenes From a Memory.
I’ve actually got some interweaved story lines in my own music, though I doubt anyone cares. The fifth chapter of Formation and Evolution is about how I encountered Special K (see this thread for background), and one of the last lines is “But I swear I’m coming back for you.” Coming Back for You is about the time I went to visit Special K, in which one of the lines is “I’m Orlando Bound”, which is a reference to an instrumental piece I wrote while I was visiting her. The most recent chapter is the as-yet-unrecorded “One Last Lullaby”. Some of the connections were unintentional, so I was pretty proud of myself once I figured it all out 
There’s quite a few examples in metal. Rhapsody Of Fire (formerly just Rhapsody) have to be the best example though. The Emerald Sword saga is an epic fantasy story told over their first 5 albums, and theDark Secret saga over the next five.
It’s all exactly as ridiculous as you’d imagine.
I don’t know if this quite counts, but there’s
Be My Yoko - The Bobs (1983)
Be My Yoko Ono - Barenaked Ladies (1989)
I Won’t Be Your Yoko Ono - Dar Williams (2000)
I don’t know if there’s any explicit connection between them all, but it doesn’t seem like it could be a complete coincidence.
…my entry would still be lightweight compared to most of those already offered. Nonetheless: “It’s My Party” > “Judy’s Turn To Cry”
.
Hank Ballard did a song called “Work With Me Annie”; Etta James replied with “Roll With Me Henry”; and Hank did “Annie Had A Baby”.
I don’t think anyone’s mentioned Pete Townshend’s Lifehouse project yet. Originally intended as a follow-up to Tommy, it didn’t appear in finished form until Townshend’s Lifehouse Chronicles in 2000, but songs from the project appeared on Who’s Next, Who Came First, Odds and Sods, The Who By Numbers, and Hooligans, and a revised version of the story was presented in Who Are You.
(By the way, I think it’s interesting how certain elements of Tommy show up in the Who’s earlier work… for example, the “Tommy” leitmotif is basically the three-chord sequence that plays under the last part of “My Generation” (where Pete sings “Talkin’ 'bout my generation” over and over while Roger yells “This’s my generation!”). Also, “Rael” on The Who Sell Out is a clear foreshadowing of Tommy… I like to think of it as the story of why Captain Walker didn’t come home.)