Depends on if you want to tank or focus on damage dealing.
DPS warriors probably want Strength (boosts damage), Agility (boosts Accuracy), and Cunning (boosts CritChance). Maybe split Cunning and Toughness if you want to have a little more durability. Make sure to TAKE OFF the Warrior's 1st-level at-will power, because that pretty much automatically makes you a tank; Cleave is a really good early-game pickup and frankly stays good all game.
Tanks want to swap Cunning out for Toughness entirely. Depending on your gear and power loadout, you could consider swapping Agility for Presence, to make your Companions do more damage so you don't have to (it also boosts your healer's healing output, too). make sure to KEEP your 1st-level at-will power -- Guarded Stance is invaluable for most of the game, until you get to its better replacements.
Just going by your name, if you want to play a Paladin build, you can make a very effective magic-using Warrior tank -- go Willpower, Toughness, and halfsies on Presence and Agility. Keep Guarded Stance until you can get Mirror Stance or Lay on Hands to replace it, and grab Entropic Winds, White Fire, and Spirit Veil as your low-level power setup. The various later-level Smite spells will be your best friend.