You are probably thinking about "Xyber 9: New Dawn" I remember this show too and it took me a lot of digging to find it. The show only aired three times in 1999, 2000, and again in 2007. The first two times it aired they only played ten of its episodes but in 2007 they played the full 22.
Jack, a precocious, blonde fifteen-year-old who is an orphan, is given the title of the Chosen One. The people of Terrana, a futuristic realm that has is amidst a war, relies upon him as the last hope to save their civilization. If Jack can achieve the Herculean task of destroying Machestro, the evil ruler of the underworld, he will be named king. Jack's greatest weapon against Machestro is the sophisticated computer Xyber 9 that is in the form of a staff. With Xyber 9's power, Jack journeys through Machestro's underworld and to other futuristic lands, fighting intergalactic evil with an ever increasing band of allies. In order to enfeeble the Chosen One, Machestro tries desperately to snare Xyber 9, for without the powerful computer, Jack would be defenseless. And with it, Machestro could spread his disease of evil throughout Terrana and beyond, conquering other worlds and ruling in his tyranny.