Tradition teaches us that the staff used by Moshe was created on the sixth day (source: Pirkei Avot 5:6) and was given to Adam, then to Noach, then to Avraham and so on. After Moshe's death, what became of the staff? Was he buried with it? Did it vanish? Is it possibly with the Ark of the Covenant?
At least some versions of Avot DeRabbi Natan 41:12 have "the staff" listed along with the Ark, the container of manna, and a few other things which was hidden away. But other lists of things hidden away (eg. Horiyot 12a) don't list it. All the lists have Aaron's flowering staff [too], so it's possible that's what was intended by Avot DeRabbi Natan and the wording is messed up a bit.
That said, there is the following Midrash in Yalkut Shimoni Tehillim 869:
מטה עוזך ישלח ה' מציון. איזה מטה זה מטה של יעקב שנאמר כי במקלי עברתי את הירדן הזה, והוא המטה שהיה ביד יהודה ומטך אשר בידך, והוא המטה שהיה ביד משה ומטה האלקים בידו, והוא המטה שהיה ביד אהרן וישלך אהרן את מטהו, והוא המטה שהיה ביד דוד שנאמר ויקח מקלו בידו, והוא המטה שהיה ביד כל מלך ומלך עד שחרב בית המקדש ונגנז, ועתיד לימסר ביד מלך המשיח ובו עתיד לרדות את עו"א
The Staff of Your Strength G-d shall send forth from Zion. Which staff is this? This is the staff of Jacob about which it is said: "Because with my staff I crossed this Jordan." And this is the staff that was with Judah [as it is said:] "And your staff that was in your hands." And this was the staff that was in the hands of Moses [as it is said:] "And the staff of G-d in his hands." And this was the staff that was in the hands of Aaron [as it is said:] "And Aaron cast down his staff." And this was the staff that was in the hands of David as it is said: "And he took his staff in his hands." And this is the staff that was in the hands of every king until the Beit Hamikdash was destroyed and it was hidden. And it is promised to be given over into the hands of the King Messiah and with it, [the King Messiah] is prophesied to strike down the idolaters.