According to Steve Sears, XWP writer and Supervising Producer, the title "Warrior Princess" was given to Xena by her troops.
Another plausible origin for the title is provided in THE DEBT II [#53], when Lao Ma says that Xena will help her to rule. "You will be my Warrior Princess."
Whatever the case, the moniker is apt. Xena is so much a warrior that the title has become an extension of her.