Utumno was the primary fortress of Melkor before the awakening of the Children of Ilúvatar. Compared to Utumno, the fortress of Angband, which figures so horribly in The Silmarillion, was just an outpost. Mordor, by comparison, was a paradise.
Utumno was the worst place that ever existed in Eä, but it was destroyed before Anar ever rose, and before the Hildor ever walked on the face of Arda.
After their initial arrival in Arda, the other Valar were forced to engage in eons of struggle with Melkor and his minions (probably explaining all of the world's geology). The thirteen greatest Valar were not able to prevent Melkor, the most powerful of all of them, from performing his mischief. Finally, assistance arrived in the form of Tulkas the Strong, last of the Valar to enter Eä, and a great foe of Melkor. With the help of Tulkas, the Valar were able to push Melkor into the Outer Dark, and bring peace to Arda for a time (the so-called 'Spring of Arda'). The Valar then set upon rebuilding the world, especially Middle-Earth, setting up the great lamps of Iluin and Ormal.
But after their labors were complete, they rested for a while. Tulkas's vigilance slipped, and Melkor stole back into Arda. In secret, he built his great stronghold in the far north of Middle-Earth, gathering his Balrogs, breeding dragons and other foul creatures, and preparing for another assault.
When Melkor was ready, he struck, throwing down Iluin and Ormal. The Valar fled Middle-Earth for Aman in the the Uttermost West, where they built their fortified dwelling, Valinor. Melkor then built Angband as a forward position, a first line of defense against an assault from Valinor.
Safe behind the Pelóri and basking in the light of the Two Trees, the Valar left Middle-Earth in darkness, illuminated only by the stars Varda put in the sky. Realizing that the awakening of the Children of Ilúvatar was close at hand, they feared to strike against Utumno without destroying the Children.
At some point in time after this, the Elves awoke around Cuiviénen. Melkor discovered this fact long before the Valar, and kidnapped elves who strayed too far from their brethren, carrying them back to Utumno. In what must be the foulest of all his deeds, beyond even the poisoning of the Two Trees, he used these hapless Elves as breeding stock, twisting them into the Orcs.
While Manwë and Varda fretted over what to do, Oromë would pass his time riding into Middle-Earth and hunting down some of the foul creatures that issued from Utumno. On one of these expeditions, he discovered the Elves near Cuiviénen. Finally, the Valar were spurred into action. First, they secured a perimeter about the Waters of Awakening. They then asaulted Utumno, fighting down to its uttermost pit, where Tulkas fought with Melkor and subdued him. Melkor was carried back to Valinor, where he was bound in unbreakable chains forged by Aulë.
After the Battle of the Powers, as it later came to be called, Utumno was completely destroyed, with all of its pits laid bare, and all of its monsters rooted out. But the Valar neglected to dismantle Angband with the same thoroughness, to their great chagrin later.
Knowledge of Utumno comes to us fourth-hand. The Valar told the Eldar while the latter were living in Valinor with them. Some of the Eldar were later exiled back to Middle-Earth and wrote down their histories. Far, far later, a strange Hobbit living in Rivendell happened to come across these histories and translated some of them into Westron. After the War of the Ring, these translations were carried back to The Shire and copied. One of these copies, the Red book of the Westmarch, somehow fell into the hands of J.R.R. Tolkien, who published them in forms we can read.
In The Lord of the Rings, Gandalf refers to the Balrog he fights as "flame of Udûn", "Udûn" apparently being another name for Utumno. If you look at Tolkien's map of Middle-Earth, you will see a small valley in the northwest of Mordor labeled "Udûn". But this later Udûn cannot be the site of Utumno, which was in the far north (unless the Change of the World was more severe than ever thought). Nine9 suggests a very plausible theory: Perhaps Sauron was trying to emulate his master.