You might try wrapping with paracord sleeve - paracord with the strands pulled out. Maybe see how that feels and how you like it. I've used the tennis racket wrap that others mentioned, but never on a hiking staff.

If you like leather, you can get 3-4oz leather, about 3/16" wide, at any good crafts store like Hobby Lobby or whatever you have there. Leather can be glued just like wood, with white or yellow aliphatic resin, liquid hide glue, contact cement, etc. If you wrapped it tightly, that would make it hold nice but it would also be (semi) permanent.