Once a player hits Level 15, they are eligible to use the Random Dungeon Finder tool. This tool, which was introduced during the Wrath of the Lich King expansion, is perhaps the greatest addition ever made to the game. Dungeon instances are a major part of the game, wherein a group of five players makes its way through a series of enemies and boss fights to get experience and/or upgrades to their gear. Instances are available at all levels from 10-85, and it is in these instances that players learn to use their skills as a group, as opposed to questing, which is usually solo. The way the Random Dungeon Finder tool works is as follows. The player opens the tool, and selects whether they want to do a random dungeon, or a specific one. A random dungeon will place the player into a group for an instance that is not revealed until they zone in. This option also gives the player some extra rewards, like an extra piece of gear or currency. If a player wants a piece of gear that they know is only in one dungeon, they can also choose to queue for just that specific instance.
They also need to choose a role, or roles that they wish to fill once they are in the group. There is a choice of three roles: tank, healer, and damage. The tank is usually a warrior, death knight, bear druid, or paladin, whose stronger armor allows them to take a hit. It's the tank's job to keep enemies stuck on them, so that they don't kill the weaker damage dealers. Healers keep the tanks alive, and occasionally need to take care of overzealous damage dealers who steal threat from the tank.
Prior to the release of the Random Dungeon Finder, players who wanted to do a dungeon had to manually search for the group, which usually involved being in a major city asking the various chat channels. The tool does all the work of finding and assembling the group, and you don't even need to be in a city to use it.
The first dungeon that I ever saw was The Deadmines, which is located underneath the city of Moonbrook in Westfall, and is the hideout for the Defias leader, Edwin Van Cleef.
Van Cleef was previously a renowned architect in Stormwind, and prior to the events of the game, was called on to repair the city after a Horde attack. The Nobles refused to pay him, however, and in his anger he formed the Brotherhood and vowed revenge. They took over Westfall, and set into motion the plan to kidnap the king that I've discussed before. Yep, they allied themselves with a dragon.
Anyway, after making your way through some mines, you eventually find yourself in a large cavern with an underground pirate ship. That's right, it's Goonies time.
The dungeon isn't particularly hard, it's basically a way for players to get their feet wet and learn the difference between playing the game solo and playing with others, but it's a fun introduction to the concept of instances. Also, dungeons are the best source of gear upgrades, so players will generally run them multiple times if they want to get a specific piece. Anyway, pre-Cata, you found Van Cleef on the ship and killed him...no big deal, really. However the Westfall chain post-Cataclysm that begins with the player investigating the earlier-referenced murders reveals that the person responsible has a connection.
Yeah, we learn from exposition that Van Cleef's daughter saw her father murdered before her eyes and vowed revenge, so she reforms the Brotherhood, kills the foster parents who knew her secret, burns Sentinel Hill to the ground, and takes up residence in the Deadmines to carry on her father's cause.
In a fun twist, she is only available in the Heroic version of the dungeon, which only Level 85 players can enter. Level-appropriate players for the regular version (13-19 or so) kill her second-in-command and find only a taunting note from Vanessa.