Rexxar (and his trusty sidekick Misha) is currently HotS' only ranged warrior (until Zarya releases). Since release Rexxar has been extraordinarily unpopular and misunderstood, with a sub 45% winrate for ages until Blizzard fixed a couple of AI bugs with Misha. Since then, Rexxar's winrate has risen to 55% or so, particularly due to his viability (or perhaps overpowered-ness on the new Braxis Holdout map). I've played Rexxar since release with a 74% winrate at a Masters level, even when he was universally regarded as clunky and underpowered, so I think I have a little bit of experience I can share with all the newfound Misha lovers popping up after the patch.

Rexxar unfortunately has had to live with the misconception that he is primarily a jungler. While jungler Rexxar is rather flashy (he can solo boss at 7), focusing on merc camps and PvE as Rexxar is a massive waste of his abilities in most cases. Rexxar has massive talent flexibility, and insta-locking in all PvE talents is almost never the correct choice. So what are his strengths beyond PvE?

Rexxar is perhaps the best solo laner in the game on maps like Dragonshire and Braxis Holdout. He won't necessarily shove the lane and tear down the enemy walls/forts like an unchecked Zagara, but he can hold a shrine indefinitely, forcing the enemy to rotate multiple heroes up in order to take control of the shrine/beacon. Rexxar has amazing zoning and peel, with the ability to safely exert pressure beyond his frail orcish body. While Misha's health pool isn't as high as most tanks, she has excellent sustain with Rexxar's E. Should Misha die, she respawns rather quickly (15 second + 4%/level) and only grants enemies 1/4 XP of a normal player kill. While you shouldn't necessarily treat Misha like a Murky, as Rexxar alone is rather useless without his companion, you should use Misha as a rearguard for your retreat, or a shield for your teammates. This allows Misha to work as a scout, you can use her as a mobile ward if need be, as her charge displaces through the enemy and can be used as an easy escape. Rexxar is also a CC machine, with a 2 second 30% slow on a 7 second cooldown and a 1.25 second AoE stun on a 10 second cooldown (and both of these CDs/durations can be improved via talents), meaning Rexxar can potentially maintain 32% uptime on his CC on multiple targets. This, combined with how Misha's stun ignores body collision, makes Rexxar invaluable in long chases and retreats. Further, depending on the build and the team comp, Rexxar can rack up a surprising amount of damage.

Understanding Rexxar's flexibility is the key to using him correctly and successfully. Before the game, you need to identify the type of threats to your team (poke, dive, AA, AP burst, ganks, etc), understand what role Rexxar should fill in your team comp (solo tank is possible if needed, solo laner, PvE, off-tank with damage) and think about how to talent and play towards these roles. If the enemy has a solo frontline and 4 squishies in the back, perhaps your role should be to use Bestial Wrath, have Misha Charge past the enemy tank, and start chunking the medic. If the enemy is dive, then maybe you should play more passive, let Misha peel instead of disrupt the backlines, and then use Unleash the Boars when the enemy tries to engage. Or maybe you don't need to be in the teamfight at all, perhaps your team has a viable 4 man that can stall objectives while you splitpush or steal merc camps and levy map pressure against the enemy (this is almost never the case and if it is you probably should have picked Abathur or Zagara).

This build plays to Rexxar's most dominant strength, his lane control. I like this build on Dragonshire and Braxis, as Rexxar can hold a shrine potentially 1v2 and even 1v3 sometimes, requiring the enemy to send almost all of their resources up to the top lane and allowing your teammates to capitalize elsewhere on the map. Maintaining proper positioning with Rexxar is vital in this role. Rexxar himself has no source of self sustain or escape, meaning damage put onto him sticks. Misha has lifesteal (which you should talent for at 4) and your Mend Pet, meaning Misha needs to take your damage for you. As Rexxar, stay behind your minion wave, potentially even by your gate if the enemy has a high threat roamer. Use Misha to harass your enemy away from the creeps to deny experience. If the enemy seems to be abnormally aggressive (or passive to the point where you have to advance further into the lane), don't be afraid to use Misha to scout a bush and ward against incoming ganks.

Level One
While Rexxar has some talent variety on this tier, I almost always choose Grizzled Bear (aka Block). If you're solo laning you won't be able to rotate to complete the Hunter-Gatherer globe quest, and even if you do, Block is almost always the better choice. Most solo laners tend to have slow but high damage auto-attacks (like Leoric or Thrall), so the reduced damage from block will almost always beat out the potential regen in a 10 second window. Keep in mind the Block only applies to Misha and not Rexxar. Situations where I'd go for Hunter-Gatherer are if I'm facing a high speed auto-attacker in lane, like a Tychus. I also occasionally grab Flare if I'm not too worried about the damage output of the other solo laner, and the enemy have a high threat ganking squad (ETC and Kerrigan or the like), as it allows me vision into nearby bushes.

Level Four
99% of the time I'll pick Hungry Bear. Rexxar's sustain is rather mana-intensive up until this point, but with this talent Misha should never die to sustained damage. Lifesteal on attack means Misha can sit on a shrine and trade auto-attacks with anyone in the game forever, while Rexxar can either attack the enemy as well if he can do so safely, or shove the lane without having to worry about his companion dying. If I have a Raynor or auto-attacker with Executioner on my team and I'm not worried about having to sustain in lane, I might take Crippling Talons to help with later game teamfights, but that's an incredibly niche situation that I almost never use.

Level Seven
By this point you should generally know how well you're trading against your other opposite. If Misha needs more help in these trades, Blood of the Rhino gives more sustain. If you don't need that sustain, Aspect of the Beast is good in lane against melee AA heroes, and is even better in teamfights.

Level Ten
Both of these ults are useful in their respective niches. Unleash the Boars has more of a teamfight CC/peel focus, whereas Bestial Wrath is great for one on one duels or if you need more damage in teamfights. A Misha with Bestial Wrath can W past the enemy front line and heavily threaten the enemy squishes with impressive damage. I prefer Bestial Wrath for solo laning, as the one on one duels are common and important to win.

Level Thirteen
Wildfire Bear tends to get maximum value, as Misha is usually sitting on one (or many) of your enemies for an extended period of time, so an additional 48 DPS per target tends to add up. Barkskin is good if you're teamfighting and the enemy has a lot of ability damage, as squishies tend to unload their cooldowns on a Misha as soon as she charges in. It can also be useful when laning against a Leoric, as his W is his main damage against Misha, although you probably won't be solo laning quite as much at this point.

Level Sixteen
This is Rexxar's most flexible tier. Primal Intimidation is amazing against auto-attackers, I choose Feign Death against mages who are smart enough to use their cooldowns on Rexxar instead of Misha (and it has amazing synergy with Spirit Bond at 20), and Critical Care is good if they have heavy sustained damage like a Lunara who keeps targeting Misha. Aspect of the Hawk is undoubtedly the worst talent of the tier, but it's fun and I might take it if I think we need more damage.

Level 20
Rexxar's Storm talents are quite flexible as well. Spirit Bond + Feign Death is a great combo if the enemy manages to land a lot of damage on you, and it gives you great damage as well. 18 seconds of AA steroids and giving Rexxar lifesteal is hard to pass up. If you took Unleash the Boars because you needed more peel, Kill Command is an amazing ult upgrade. It's fairly easy to land on the entire enemy team, and it's great to set up wombos with the 1.5 second root. Frenzy of Kalimdor is a decent hybrid between the two as it adds damage and CC, and is useful if you need more PvE pressure as well. Hardened Shield isn't bad, it's just outclassed by the other options. If Rexxar's facing heavy burst, then Feign Death/Spirit Bond would be a better combo. If Rexxar's solo tanking, then a 5 man root would be more useful in general.

This build is useful on maps like Cursed Hollow, ToSQ (although your role might be to solo and if so, you'll want a hybrid between this and the solo laning build), ToD, and Battlefield of Eternity. These maps tend to encourage fighting in cramped corridors, meaning Misha's W can fairly easily land multi-person stuns.

Level One
Hunter-Gatherer is marginally better here than on the solo lane because you might be rotating more, but even so I still prefer Block most of the time. Flare does become a lot more useful, it can ward against incoming Thrall sunder flanks and these maps tend to have limited vision, so the Flare can be incredibly important if used correctly.

Level Four
Same as the solo laning guide, Hungry Bear almost always.

Level Seven
Blood of the Rhino is useful in protracted engagements but the CD reduction on Rexxar's most impactful teamfight ability is just too good to pass up.

Level Ten
This largely depends on the team compositions. If you're the team to dive and engage, Bestial Wrath allow Misha to stun through the frontline and chunk an enemy medic down in a matter of seconds. If you need the peel to stall enemy engages or to set up for a wombo combo, then Unleash the Boars is good, particularly once you get the level 20 upgrade.

Level Thirteen
Wildfire Bear usually, occasionally Barkskin. See Solo Laning for explanation.

Level Sixteen
See Solo Laning for explanation, generally I pick Primal Intimidation here.

Level Twenty
Spirit Bond for burst and if you took Feign Death, Kill Command for setting up wombos and peeling, Frenzy of Kalimdor for more sustained DPS and some peel.

Personally hate this build, only use it on BHB or potentially Garden of Terror but even there I think a Sonya would be more useful than PvE Rexxar. I think giving up Hungry Bear at 4 and having to take Bird of Prey at 7 cripple his teamfight viability.