I don't remember what the Legend trees look like, so I'm referencing this character planner.
I assume it's accurate. I played a warrior in The Legend, so I'm most familiar with the Might skills.
Warriors work well with human and elven units, due to the Training, Iron Fist and Bowmen Commander skills - you should definitely get them if you're using those unit types. Anger and Rage Control are also great to be able to use your Spirits of Rage more often. I found Master of Spirits to be a bit double-edged - if your spirits level up too quickly, their rage requirements may get out of hand.
Tactics is a lot more useful than it sounds. Being able to arrange your troops before combat begins can help you set up an initial attack, place weaker units out of harm's way, or get your troops out from behind battlefield obstacles. It's especially helpful during certain fights that place your troops in the middle of the board, instead of at one end.
I sort of ignored Night Ops in The Legend, but in Armored Princess I made extensive use of it to give myself an edge in difficult battles - with Night Ops, waiting until the sun sets can give you a definite boost, especially if you find other nighttime-focused equipment (I don't remember if there's any of that in The Legend).
Frenzy's pretty decent - what it actually does is provide the listed bonus to a troop for the rest of the battle every time it kills an enemy stack. This is particularly amusing when your Knights kill two or three troops at once with Circle Attack.
Dark Commander of course is worth getting if you use a lot of undead units, but I didn't.
Outside of the Might tree, Mind has a few bonuses of obvious value (XP, gold, etc). Don't worry too much about gold, though, you'll find a ton of it anyway. Scouting is cheap and useful, and I found Inquisition handy because I had trouble recruiting inquisitors (can you recruit them at all in Legend, or is Inquisition the only way to get them? I don't recall), but it's at the bottom of the tree. Magic is useful for any character; as a warrior you'll most likely be using it for battlefield support, with spells like Helplessness and Dragon Arrows. Necromancy is also useful to reduce your losses after combat.