It seems, according to Tolkien's essay "The Istari" that the Wizards brought their staves with them from the Undying Lands. At least, that was the case with Gandalf.
Of this Order the number is unknown; but of those that came to the North of Middle-earth, where there was most hope (because of the remnant of the Dúnedain and of the Eldar that abode there), the chiefs were five. The first to come was one of noble mien and bearing, with raven hair, and a fair voice, and he was clad in white; great skill he had in works of hand, and he was regarded by well-nigh all, even by the Eldar, as the head of the Order. Others there were also: two clad in sea-blue, and one in earthen brown; and last came one who seemed the least, less tall than the others, and in looks more aged, grey-haired and grey-clad, and leaning on a staff.
However, when Gandalf returned to Middle-earth as Gandalf the White, I believe his new staff was given to him by Galadriel, so he might have been the exception, not the rule.