So I'm starting a new DK, and I did some reading to find out that frost is suggested as the best way to level up right now for damage dealing. So my questions are:
short answers:
yes, frost
DW or 2H - just go with your best weapon(s). we have both Threat of Thessarian and Might of the Frozen Wastes as baseline passiv abilities. So you can switch between using DW and 2H without any hassle.
Leveling is best with a 2H since you play all 3 specs if you decide to try them out Sometimes its nice to switch into blood and just take down a whole bunch of mobs (at the moment I'm leveling my dk from 85-90 in blood).
2H > DW for lvling since the burst is higher, and its easier to swap to blood for dungeons or (god forbid) you run into something challenging in this game.
Long version: Frost has more burst than unholy, making it better since things tend to die quite fast. 2handed results in even more burst than Dualwield, making that better (the overall dps is about the same). Frost presence is better than unholy presence because it makes Frost strike cheaper by almost 50% (35 -> 20 RP) and generates more RP for you.