So you've made it to Outlands! Welcome! The land of the Burning Crusade - home of lurid skies and lurid gear :)
Level 60 gives us an important tool for leveling: Death & Decay. Now we can really aoe! Combined with pestilence to spread your diseases, and blood boil, you can now do some serious damage to as many mobs as you can pull. Your leveling will never be the same. Read on, McDuff for more suggestions on burning your way to Northrend...
1. Talent spec 60-68. There's some real goodies here. As I mentioned yesterday, after you get Pale Horse from Unholy, I recommend going blood all the way for very nice damage combined with superior health regeneration for constant unceasing grindage. Just follow the dps talents down the tree; by level 68 your spec should be something like this. For all but the most difficult elite quests/mobs, you should have no problem soloing them with this spec. I stay away from rune tap, mark of blood, or vampiric blood because I want to maximize my dps, whether soloing or running 5-mans. If you like, you could take a point or two in rune tap, but you probably won't need it. Just death strike if you have any problems. At 61 you'll get path of frost which actually can speed leveling quite a bit - especially in Borean Tundra, but is useful in Zangamar etc as well. At 65 you get Horn of Winter which provides you and your party a nice buff. Keep it up at all times! At 67 you'll train rune strike as well as pick up Heart Strike in the blood tree - both are huge upgrades.
2. DPS considerations. By now you have some powerful tools for dps.
For single or two-mob pulls, you should:
Icy Touch > Plague Strike > Blood Strike > BS > Death Strike > Death Coil
DS > DS > DS > Death Coil
you could substitute Obliterate for Death Strike for the next 7 levels but once you have improved death strike and glyph, you'll do more damage and the healing is key as well. At 67 you'll be spamming Heart Strike and never use Oblit again.
For multiple mob pulls, you should:
Icy Touch > Plague Strike > Pestilence > Death & Decay > Death Coil
after that you can blood boil, making sure to keep spreading diseases with pestilence and D&D when it's up. If your health drops, Death Strike.
At 67 for single/double target:
Icy Touch > Plague Strike > Heart Strike > Heart Strike > Death Strike > Death Coil
HS > HS > HS > HS > DS
You should remove Blood Strike and Obliterate (if you have it) from your bars completely. You may choose to put Rune Strike on your bars - and you should use it every time it procs because it's a dps upgrade. I didn't put it on my bars, I just macro'd it to all my strikes like so:
#showtooltip Heart Strike
/cast Heart Strike
/cast Rune Strike
Any time your quest involves killing mobs, my recommended approach is to mount up (land mount is easier to not lose agro), and run through the area, pulling as many mobs as you can. Once you get the knack of aoeing, and keeping your health full with the aforementioned Vendetta and Death Strike, you can pull larger and larger groups. Start with small groups, and graduate to bigger mob packs. By the time you're on the ravagers near Zangamarsh, you should be pulling 5-6 mobs and burning them down, fast. Don't forget to mitigate some damage by using your Icebound Fortitude and Anti-Magic Shield.
3. Gearing. At some point, gear drops and/or quest rewards will start proving an upgrade to your starter blues. Prioritize your stats like so: strength, strength, strength. After that, you can try to get some hit and expertise. It's not on a lot of leveling gear, but it will help a lot for your dps. If you get gear with gem slots, consider gemming hit/exp if you don't have much. Lacking hit is another good reason to focus on green quests/mobs. Yes, it's easy to solo orange elites. But it's even easier to solo green ones. After hit/exp, crit and armor penetration are best, followed by haste, agility, and attack power. DO NOT make the noob mistake of equipping gear with int, spirit, spell penetration, or, god forbid, spell power. Plate with any of those stats is NOT for you despite it being plate. Leave it to the pallies. :) If you get tanking stats like defense, dodge, or parry (not block value), you may choose to start building a tank set although I wouldn't recommend it until 68. But don't equip those while soloing unless an elite is giving you trouble (more on that later).
4. Miscellaneous. Spend a little gold on gemming any slots with northrend green-quality gems. They cost 2-8g on most servers. Also get your glyphs. Get the ghoul and pestilence minor glyphs, and Death Strike and Dark Death for now. Don't bother to enchant gear as you'll discard it too fast, unless you have money to burn. Save the rest of your gold for flying skill and a mount - buy those as soon as you have the money, which I had around level 63 on my 'poor' DK. If you are not in a huge hurry to make it to 80, you may choose to take one or two professions. I recommend for leveling you take leatherworking because it's so easy to get caught up to your level and you don't have to worry about 'yellow dot agro.' If you like, you may also take herbing or mining. All the gathering professions will make you more more gold more easily as you level unless you like the AH game (but then you're not really leveling, are you? You're playing the money game). Send all your green boe drops to an enchanter to disenchant. Even low level greens yield valuable materials, as not many people farm them and they're necessary for leveling enchanting. Do try to get the instance quests and find a decent group to complete them with. Also, if you haven't heard this before, stay in Hellfire Peninsula until you've exhausted almost all the quests. Doing green quests/mobs yields wonderful xp and you should certainly be able to do all the group quests solo, even the Faralon Giants quest. Then exhaust the quests in Zangamarsh. After that you may quest in Terrokar, although this time around I went straight to Nagrand because I was 65 after Zanga and the Nagrand quests are grouped a little better in my opinion. I also admit to a fondness for the Nesingwary quest chains.
Well, that was a lot of info! Phew!
Good luck, and have fun in the Outlands!