There are a lot of good answers already about figuring out that it is magical, but I am not sure they are really fully addressing the question of finding it.
If you want to be subtle, both for the readers and for NotBilly and his/her companions, then a very plain staff is a good starting point. It can even be visibly plain, but gradually shift over time, or look different in a certain light, but on the surface it should just look like a normal, utilitarian wooden pole that can be used for holding things up or hitting someone, just like any other length of reasonably sturdy wood.
Finding the staff
It should be found at a time when something like that is needed, maybe not precisely a wooden staff; it might just be the best option available at the time. For example, our hero and his intrepid band stumble across a small group of bandits and end up driving them off, but one of their party is injured. The injury is bad enough that they need to make a sledge or stretcher to carry him, this pole that was leaning against a tree is just one of the pieces of wood used for the structure of the sledge, and other thing scavenged from the bandit camp get more attention. Perhaps there is a richly-lined and warm fur cloak or a supple and well-balanced bow and a fine quiver of arrows. After getting to civilization and taking the injured person to get medical attention, the cloak, ropes used in the sledge and this staff simply get packed away with the rest of the gear.
Later, someone (the bandits, wild animals, whatever makes sense) attacks the group at a time when they least expect it, NotBilly is near the gear and unarmed, the sledge-pole is nearby, he uses it to protect himself, and the next day, there he is, using it as a walking staff as they go.
If NotBilly is the type of person who normally wields a sword, it would be unnatural for him to suddenly switch to a staff, even if he likes its balance and it "just feels right" in his hand; as soon as his current use for it is over, he would tend to swap back to the sword. It might be easier to have a non-combatant develop a flair for combat with a staff. On the other hand, having a sword-wielder gradually stop going for his sword and finding that he's reaching for the staff might be a clue that something is going on. At first, perhaps he tells himself he needs the reach on a taller opponent, or perhaps he doesn't have time to drop it and grab for his sword from the sheath, but later he leaves the sword untouched at his belt, and later he finds it is getting in the way and he leaves it in his pack.
Abilities
As noted in prior answers, durability, balance, and improved skill when using the weapon are very helpful here. It could also resist NotBilly being disarmed -- he is able to keep a grip even in circumstances where he would be expected to drop it or have it knocked out of his hands. On the other hand, he is surprisingly adept at disarming other opponents.
He might develop an uncanny knack for subduing an opponent without causing major bodily harm, either destroying the weapons of his opponents or knocking them far out of reach, or managing to stun or knock someone unconscious without killing them. Blows that might otherwise be expected to break bones don't, but the opponent still stays down. Consider that a wooden staff is often the classic weapon of peace-loving characters, so perhaps this is a weapon that subdues aggressive instincts and increases protective ones in anyone who is touched by it. Perhaps it needs a flesh contact to work, so wearing gloves causes NotBilly to lose his new skills, and hitting someone where they are armored doesn't spread the pacification as well as knocking them on the ear or a bare ankle.
