Hearthpwn

There have been quite a few fatigue warrior decklists that have come out, but they seem to underestimate the power of doomsayer and deathlord. They either use one or the other, or treat one or both of them as one-offs. The theory behind using both is simple: They're both incredible against aggro to stall the early game and allow you to thrive in the middle-late game, and most importantly, they are also really good against control in that they increase your brawl value (and in the case of deathlord, expedite your opponent's fatigue by pulling a card out of his deck). How does doomsayer increase brawl efficiency? Several reasons:

1) If the opponent lacks removal or owl, the common response to doomsayer is to kill it with your board. But what do they do with their remaining mana? They put more minions on the board! The alternative to this scenario is the warrior plays a minion and they use their board to trade with and then play another minion with their mana, limiting brawl's efficiency by having fewer minions on the board at the same time.

2) If the opponent uses an owl on the doomsayer, and then goes face, you not only have an owl now in play to "compete" in the brawl, but you also have your own doomsayer. Now, whatever minion(s) they had to begin with have a lesser chance to emerge victorious from the brawl.

And if the doomsayer draws a removal card, then you simply pat it on the back for being a two drop that provokes a valuable removal card before your late game threats (ysera, dr boom, etc).

Deathlord is bit more obvious in that it often forces your opponent to flood the board with minions to kill it, and upon doing so another minion is pulled from the deck, meaning an extra minion of theirs is guaranteed to lose the brawl.

Everything else in the deck is pretty standard, and is just tweaked after a lot of experience playing this deck. No need to run 2 war axes. Cruel task master isn't that great, especially against other control decks. There is no card draw in this deck for the simple reason that your win condition against other control decks is fatigue, and also your game plan is very much a "waiting" game in that you just armor up every turn, gaining armor through bash, armorsmith, shield maiden etc, tempting your opponent to flood their board, only to get brawled. Since you don't have a real win condition card (except for maybe Justicar against other fatigue warriors), card cycle isn't necessary.

And as for strategy:

Against aggro: use every possible resource to slow the game down. Doomsayer on turn 2/3, deathlord (which you should mulligan for), owl early (unless you suspect it is a mid-range pally, in which case you NEED owl for Tirion), etc.

Against control: If they play Acolyte, your goal should be to MAXIMIZE its card draw. Hit it with revenge, attack it with armor smith, hit face with death bite to get the whirlwind effect. I have never once lost to a control warrior, so do not worry about "wasting resources" that might be important later on. The win condition here is fatigue, and you want to speed that up as fast as possible. The only caveat is that deathlord should only be played once you have either a brawl, execute, or BGH in hand, so that you don't lost by turn 5 because they pull a ragnaros or other big minion before you have the resources to deal with it. Also, hold your deathlord until they play at least one or two "draw" cards. Once you play deathlord, it screams out fatigue warrior, and a good player will now hold onto their draw cards. This deck otherwise looks very much like a normal control warrior, so it hides itself very well.