Deadmines

First off why goto an instance at all? They are much more difficult than other areas of the game, usually give lower xp than soloing as well. Pretty much they are just for loot and quests that give you loot.

Here are a list of all deadmines related quests.

These are the quests that are not in the instance, but are in the mine area outside. You have to fight through some defias around level 17-19 and then fight some skeletons to a boss zombie for Oh Brother, the memories can be collected off any of the undead at random. You get both of these quests from the same NPC in the Dwarf District of SW. You can pull up a map on thott.
Collecting Memories - Reward is Mail boots or Leather Gloves.
Oh Brother. . . The reward is a 2h Axe

There are 2 quests inside the instance. One is to kill a goblin shredder (A required boss to advance). The other is to kill VanCleef the last boss of the dungeon.
Underground Assault gives mail gloves or a wand.
The Defias Brotherhood This gives very good rewards. Mail pants, Leather Tunic or a Staff. This starts as a quest line from Stoutmantle in Westfall at level 14 and has the same name at the beginning of the quest line.

So, what other items can you get from this instance? Following is a list of items uniquely dropped in the Deadmines. This does not include world drops, that you will likely see a few of, since they are so random you cannot rely on ever seeing one.

Rhak'Zor
This is the first boss you fight. He is immune to cold and is a pretty easy fight. There are two additional mobs in the room with Rhak'Zor. The best strategy is to attempt to body pull one of the three, typically Rhak'Zor himself, and kill a single mob in the hallway before dealing with the other two. Don't rely on frost nova to get Rhak'Zor off you as a mage.
Rhak'Zor's Hammer

Sneed's Shredder
Sneed's Shredder is not immune to cold or snares. This leaves a lot of options open for kiting. Back when talents first went in he could be soloed pretty easily by a level 18 mage. An important note is that the first release of Talents allowed a level 18 Mage to ahve as many talent points as a level 28 does now.
Buzzer Blade Common Drop
Buzz Saw Rare Drop

Sneed
After killing the Shredder you have to fight the pilot. The only difficult part about fighting him is not expecting another fight immediatly after the last. So, be ready! Gold-flecked Gloves Common Drop
Taskmaster's Axe Rare Drop

Gilnid
This fight takes place in the foundry room. You need to clear a large number of engineer type goblins before reaching Gilnid. One type of goblin creates a mechanical when it first gains aggro to attack another member of the group.

Gilnid always comes with an add or two. You should focus on the adds first, since they are pretty easy to take down. Also just try to keep good aggro on all adds so your healer doesn't get hit when they start healing.
Smelting Pants Common Drop
Lavishly Jeweled Ring Rare Drop

Mr. Smite
Smite is a Tauren Warrior with warstomp. He has 2 hidden adds from the stealthed defias near him. Kill the adds first, because Smite's DPS just goes up through the fight. At the beginning Smite isn't much of a problem, and the adds are a lot quicker to kill than him.

One strategy for engaging the adds first is to stand well back from the base of the bridge and use an AE damage attack at the base of one of the pillars at the bottom of the bridge. This should only pull one or both of the adds. Leaving you to deal with Smite alone later.
Smite's Reaver Common Drop
Thief's Blade Common Drop
Smite's Mighty Hammer Rare Drop

Cookie
He is a murloc and the ship's cook. Most groups skip him but you can find him around the backside of the ship.
Cookie's Tenderizer Common Drop
Cookie's Stirring Rod Rare Drop

Captain Greenskin
This is the last boss before VanCleef and he patrols the top decks of the ship. The difficulty here is that he wanders the top deck and can aggro the group while fighting other mobs on the stairs up to the top.

It may be best to station a resser at the back of the party in case of a wipeout. The resser can run off the back of the ship and swim around to the staircase where the Smite fight occurs to get back up on the ship.
Impaling Harpoon Common Drop
Emberstone Staff Rare Drop

Edwin VanCleef
This is what you have been waiting for. He spawns 2 bodyguards immediately, and 2 more later in the fight. Best to take out the bodyguards fast so you do not get overwhelmed. The running resser can also be used here to recover from a wipe. This strategy works best if you go around back where Cookie is on your way up to the top deck.
Corsair's Overshirt Common Drop
Cruel Barb Common Drop
Cape of the Brotherhood Rare Drop
Blackened Defias Armor Rare Drop