i would say arms until you get duelweild, than fury. fury is good until the low to mid 50 than arms starts to be attractive again. but most ppl do a hybrid arms/fury since most of the BC tier talents sucked. in outland you should go prot.,

the priest should be adjusted to keep the warrior alive, either more damage or more healing.

this was the combo i did to level my warrior. a friend had a priest. (not multiboxing) this would be good if your ultimate goal is to do instances, since you control the two hardest classes to get for an instance run. but leveling is slower than other 2 class combo's. the warrior can't handle more than 2 mobs at a time before your priest is full time healing and than OoM. so you have to wait for the priest to drink and eat all the time. plus you lack good CC. so if you get a runner and he brings some adds, your group can quickly get in over it's head.

this group is the definition of grinding.