I thought it'd be fun to cobble together a soundtrack of sorts for the travelogue. Basically these are songs that, for whatever reason, I associate with sections of Azeroth. Generally the lyrics are at least thematically appropriate, even if they reference things distinctly from our own world.
I'll also include links to YouTube, so those not familiar with the songs can hear them.
Tirisfal Glades - Stumpside, by Rasputina
The Western Plaguelands (the ruins of Andorhal) - The Village Green, by the Kinks
The Eastern Plaguelands - Atrocity Exhibition, by Joy Division
Undercity (the party scene) - Legs and Tarpaulin, by Cinema Strange
Alterac Mountains (reminisces of Dalaran) - The Legionnaire's Lament, by the Decemberists
The Wetlands (the Deepwater Tavern) - The Mariner's Revenge Song, by the Decemberists (it's a long video, but well worth watching)
Loch Modan - Pastoral Symphony (5th Movement), by Beethoeven
Loch Modan (Thelsamar) - Sh'boom Sh'boom , by the Chords
Dun Morogh - January Hymn, by the Decemberists
Ironforge (the Great Forge) - Come On! Feel the Illinoise! by Sufjan Stevens (this is a song about the World's Columbian Exposition, held in Chicago in 1893. It makes me think of Ironforge for some reason; don't ask me why)
Ironforge (Tinkertown) - Birdhouse in Your Soul, by They Might Be Giants (if They Might Be Giants existed on Azeroth, they'd totally be a gnome band)
The Badlands - Violin Concerto in D Major, Opus 77, by Brahms (and yes, I did first hear this piece while watching There Will Be Blood, another great film)
Blackrock Mountain - The Stone Tower Temple, from the Zelda Reorchestrate version of the Majora's Mask Soundtrack (suggested by Farsider)
Elwynn Forest (Goldshire) - Do You Remember Walter, by the Kinks
Stormwind City (the Mages' District) - Brandenberg Concerto No. 6 - iii, by Johan Sebastien Bach
Stormwind City (the Pig and Whistle) - In the Mood, by Glenn Miller
Westfall - Kids with Guns, by the Gorillaz (suggested by Saranus) -or- When the War Came, by the Decemberists
Duskwood - Silent Hedges, by Bauhaus
Duskwood/Deadwind Pass (the Ralmanni) - Wonderlust King, by Gogol Bordello.
The Blasted Lands (The Angel that Speaks with the Voice of a Thousand Friends) - Red Right Hand, by Nick Cave and the Bad Seeds, covered by Pete Yorn (as heard on Hellboy)
Stranglethorn Vale (Booty Bay) - Brazil, by Xavier Cougat
(I actually wanted the version sung by Geoff Muldaur, as heard in the amazing Terry Gilliam film, Brazil. That one's not available on YouTube, but this a good alternative with crazy-cool spastic animation).
Darkshore (Aubderine Inn) - The Third Man Theme, by Anton Karas (The music starts at 0:55. This pretty much is the tune played by the innkeeper on her koto, and a reference to the film. The Third Man is quite simply one of the best films ever made, and arguably Orson Welles' finest role).
Darkshore (forests) - Everyday is Like Sunday, by Morrissey
Ashenvale - Suite in A Major, by Dvorak
The Barrens (Drub's farm) - Don't Fence Me In, by Cole Porter as adapted from a poem by Bob Fletcher, and sung by Bing Crosby and the Andrews Sisters
The Barrens (Ratchet) - Singapore, by Tom Waits
Durotar (Sen'jin Village) - Say Hey, by Michael Franti & Spearhead
Orgrimmar - Romeo & Juliet, Act II Finale, by Prokofiev (I know Romeo & Juliet doesn't sound right for the orcs, but just trust me on this, particularly at the 1:55 mark)
Mulgore - Simple Gifts portion of Appalachian Spring, by Aaron Copeland (After some thought, I figured this works better in Mulgore than it does in Feralas. Feralas should be more mysterious and foreboding.)
Thunder Bluff - Witch of Endor, by Moondog (the Endor in the title has nothing to do with Star Wars so far as I can tell, but it's still a wonderful piece from one of the most iconoclastic musicians of the 20th century.)
Stonetalon Mountains (Venture Company) - Rox in the Box, by the Decemberists
Stonetalon Mountains (Sun Rock Retreat) - An Angry Blade, by Iron and Wine (suggested by Saranus, though for the Blade's Edge Mountains)
Tanaris (Gadgetzan) - White Light/White Heat, by the Velvet Underground
Tanaris (Lost Rigger Cove) - Sloop John B, by the Beach Boys (suggested by Saranus)
Tanaris (Zul'farrak) - Cities in Dust, by Siouxsie and the Banshees
Silithus (preparing for Ahn'qiraj) - This is Why We Fight, by the Decemberists
Azuremyst Isle - Micah, by Russian Circles (suggested by Adam Huxhold)
The Ghostlands - Xibalba, by Clint Mansell, from The Fountain soundtrack (I'm one of the three or four people who actually liked Darren Aranofsky's The Fountain. Regardless of the film, I think this track goes well with the ambience of the Ghostlands.)
Eversong Woods (Lyria Songflight) - Yankee Bayonet, by the Decemberists
Hellfire Peninsula (the Dark Portal) - Mars, Bringer of War, by Gustav Holst (Hopefully this isn't too cliche)
Zangarmarsh - Teardrop, by Massive Attack, covered by Jose Gonzalez (Suggested by Saranus)
Netherstorm - Shadowplay, by Joy Division, covered by the Killers (For whatever reason, I think that this cover goes better with Netherstorm than does the original)
Netherstorm (Pazshe in combat) - Atman, by Rodrigo y Gabriela (I originally used this for the Stormspire, but it's too fast-paced. Atman's a much better fit for Pazshe when he's kicking ass and taking names)
Shattrath City (the Lower City) - Into Each Life Some Rain Must Fall, by the Inkspots and Ella Fitzgerald
Terrokar Forest (outside Tuurem) - Death of Aase, by Edvard Grieg
Shadowmoon Valley - New Dawn Fades, by Joy Division
Shadowmoon Valley (Hand of Gul'dan) - King Volcano, by Bauhaus
The Howling Fjord (Vengeance Landing) - They Walked in Line, by Joy Division
The Howling Fjord (Skorn) - Over the Hills and Far Away, by Nightwish
The Grizzly Hills (the black market at the camp) - I'm Waiting for My Man, by the Velvet Underground
The Grizzly Hills (the Kirovi) - Nad Synom Donom, sung by the Red Army Chorus (An amazing piece. For extra fun, check out the creepy Russian ultranationalism in the comments section.)
Zul'drak (Zol'heb) - Powerslave, by Iron Maiden
The Storm Peaks (Valley of Ancient Winters) - White Winter Hymnal, by the Fleet Foxes (as suggested by Saranus)
Crystalsong Forest (memories of old Dalaran) - The Engine Driver, by the Decemberists
Dalaran (Runeweaver Square) - These Days, by Nico
Dalaran (Violet Citadel) - Reverie, by Debussy
Dalaran (Silver Enclave/Galone) - Panic, by the Smiths.
The Underbelly - Interzone, by Joy Division
A Point of No Return (Destron and Daj'yah's walk through Orgrimmar) - There's a Light that Never Goes Out, by the Smiths (I was trying to decide between the original Smiths version, the solo Morrissey cover, or the Spanish-language cover by Mikel Erentxun. They all work pretty well, but I finally went with the original.)
Borean Tundra (peon training) - Rise Above, by Black Flag
Wintergrasp - Life on Mars, by David Bowie
Dragonblight (Wrathgate) - Sarabande, by Handel
Azjol-Nerub (history of the azi'aqir) - Alhazred's Vision, by Nox Arcana
Icecrown Glacier (Shadow Vault) - The Eternal, by Joy Division
Icecrown Glacier (Cathedral of Darkness) - Day of the Lords, by Joy Division
Kezan (voyage to Kezan) - Beneath the Southern Cross, by Richard Rodgers
Kezan (Swindle Street) - God's Away on Business, by Tom Waits
Kezan (Gallywix's party) - Hurricane Season, by Trombone Shorty (Trombone Shorty is seriously awesome; you should all check him out)
The Lost Isles (exploring the island) - Island in the Sun, by Weezer (I've been wanting to put in a Weezer song since starting this soundtrack)
The Lordaeronian Front (escaping Gilneas) - Peer Gynt's Homecoming, by Edvard Grieg
Orgrimmar Redux (Darkbriar radio) - 20th Century Blues, by Noel Coward
Orgrimmar Redux (talking to Daj'yah in the lodge) - Wrapped Up in Books, by Belle and Sebastian
Bilgewater Harbor (first sights of the city) - Rhapsody in Blue, by George Gershwin
Mount Hyjal (approaching Nordrassil) - Crystallize, by Lindsey Stirling
The Southern Barrens (night attack) - Lucretia, My Reflection, by the Sisters of Mercy
The Skywall (entry and exploration) - Havayeh Garyeh, by Homayoun Shajarian
Booty Bay (arrival in the Lazy Turtle) - I Like the Way You Smile at Me Baby, by... some guy at Bethesda? This was a musical piece in the flawed but fun Call of Cthulhu: Dark Corners of the Earth. So far as I can tell it's an original composition, but it does a great job of capturing the '20s style.
Booty Bay (announcement of Stonard's fall) - Broken Hearted, by Aileen Stanley
Booty Bay (at the Frolic in the Tropics) - Japanese Sandman, by Richard Whiting, covered by Vince Giordano and the Night Hawks (got this from the Boardwalk Empire soundtrack—great show, by the way)
More to come...