Great, now THAT'S out of the way:
Our Founding Bothers
Back in the days of the First Age, when the Valar woke up every morning to set out and create a world of beauty and wonder, Melkor, one of their number and Middle-Earth's answer to Satan, looked upon what they had wrought and declared: "Gay." So he did what anyone of his disposition would and started smashing it to all nine hells. The early First Age was loaded with his exploits, with Melkor and the other Valar battling with mountains and continents as Arda burned beneath their feet. Eventually, the Valar managed to stabilize the planet, kicked Melkor off to the north, and fucked off to Valinor in the far west. Mordor was a remnant of the ruckus that went down across all of Middle-Earth, but being so far east compared to Beleriand, where most of the interesting shit happened in the First Age (to the point where Khazad-dum, featured in the Lord of the Rings, was just a myth of those peoples) it mostly sat empty, except for Shelob and her ancestors setting up a few flats in the eastern mountains.
That all changed when Melkor was thrown down by the Valar in the War of Wrath. Being much less of a destructive crybaby than Melkor, Sauron (at this point a lord of magic and werewolves) surrendered to the Valar. But when he learned he would have to submit to their justice, he fled for his life, settling in Mordor because he thought it looked pretty cool.
During the early Second Age, Sauron raised up his fortress of Barad-dûr, the biggest and baddest fortress seen since Melkor's stronghold of Angband fell in the War of Wrath. (The central tower was five miles high, if you take the movies as an accurate depiction.) Then he went out into the world in the form of Annatar, Lord of Gifts, helping the elves to make the Rings of Power. But they were all of them deceived, for another ring was made. Sauron took up his Great Ring and declared himself King of the World, sending his armies of orcs and trolls out to conquer, pillage, and probably do other stuff.
Sauron, like his master, was a dick of an overlord and was hell-bent on the domination of the peoples of Middle-Earth. Mordor was invaded and put to the sword by the Nümenorians, who were upset that someone was stealing their thunder, and like his deceptive mentor, Sauron feigned honorable defeat in front of Ar-Pharazôn, the king of Nümenor. After which he was taken prisoner on Numenor and began his typical antics there, which resulted in Melkor-worship and the sinking of Numenor by Erú-Illuvatar. Sauron pulls a "BAIL BAIL BAIL" and his spirit returns to Mordor.
And it doesn't stop there yet. After Sauron regains his strength and grows a new army of orcs and trolls, he puts on his "King of the World" suit again, yells at the remaining Numenorians to bend the knee, and goes apeshit when they don't. Once again, he has to be put down, this time by the Last Alliance of Elves and Men. (The Dwarves would have shown up, but they were backed into Moria and Erebor and couldn't make the date.) Sauron is destroyed, but his Ring is saved, and he is able to keep going as a whispery spirit until such time as he could rebuild his body. The Numenorians build the kingdoms of Gondor and Arnor, with Osgiliath as the capital and Minas Ithil being the largest fortress set upon the mountains to keep watch over Mordor.
Time passes and the fortresses surrounding Mordor fall into orc hands due to human negligence and a nasty black wind from the East that sickened the land's wardens. Angmar rises up in the North, Arnor falls, and after a lot of battles the Witch-King of Angmar flees to Minas Ithil (now renamed Minas Morghul) to keep the heat on until Sauron returns. Eventually, two halflings and a mutant junkie halfling do simply sneak into there.
The rest, you know.
Places to Visit!
Mordor is more than just an arid plateau with its toxic streams and choking atmosphere, it has a whole rainbow of variety- to its evil nature.
Plateau of Gorgoroth
A ashen wasteland, where Sauron held court in the fortress of Barad-Dûr, which has a lovely view of Orodruin (Mt. Doom). This is where most of the action happens.
Before exiting the black gate, an orc needs a good implement of slaughter as well as a decent suit of armour, which he receives from the forges and armouries of the valley of Udûn. Thanks to the contribution of slaves, the forges spew out a steady supply of wicked tools and suits fit for orc raids.
Orcs need to eat, and the lands of Núrn supply them with a steady diet of meat and maggoty bread, courtesy of the, you guessed it, man-slaves. Volcanic ash works wonders on the crops, supplying a constant stream of fertilizer.
The ruins of ancient Nümenorians that lived there during the days of Gil-Galad and Isildur. Now the ownership like with all the failures of the Edain, has been moved over to lesser creatures like orcs.