Where did they come from?
We know that at least Gandalf arrived in Middle Earth with his staff; Unfinished Tales tells us as much (emphasis mine):
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 Dunedain and of the Eldar that abode there), the chiefs was 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 the 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.
Unfinished Tales: "The Istari"
We know that at least Saruman had one, and it seems likely that the other wizards did as well; Saruman specifically mentions "the rods of the Five Wizards" shortly before Gandalf breaks his staff, and that seems like an odd comment to make if they didn't have them (although it's not impossible that he was speaking metaphorically). Whether they also came from Aman, or if they were fashioned later, is unknown.
We do know that they can be fashioned later, since Gandalf gets his new White staff in Lothlórien:
'Naked I was sent back - for a brief time, until my task is done. And naked I lay upon the mountain-top.
[...]
'Thus it was that I came to Caras Galadhon and found you but lately gone. I tarried there in the ageless time of that land where days bring healing not decay. Healing I found, and I was clothed in white.
The Two Towers Book 1 Chapter 5: "The White Rider"
Saruman also gets another staff, after he leaves Orthanc:
On the sixth day since their parting from the King they journeyed through a wood climbing down from the hills at the feet of the Misty Mountains that now marched on their right hand. As they came out again into the open country at sundown they overtook an old man leaning on a staff, and he was clothed in rags of grey or dirty white, and at his heels went another beggar, slouching and whining.
'Well Saruman!' said Gandalf. 'Where are you going?'
The Return of the King Book 2 Chapter 6: "Many Partings"
It's unclear if having it affects his power; both Gandalf and later Frodo suggest that Saruman has essentially no power left (more on that shortly), but we never see him try to use any power other than his hypnotic voice
What do they do?
This is very unclear, and somewhat self-contradictory, although the balance of evidence suggests some link between the power of a wizard and their staff.
In an answer to a related question, DVK summarizes some of the inconsistencies. Basically, nearly every time we see a wizard performing magic, he uses a staff. On the other hand, Saruman doesn't take Gandalf's staff when he imprisons Gandalf in Orthanc, something that seems like a critical oversight if the staff is critical to doing magic.
It's notable that Saruman is very de-powered after Gandalf breaks his staff. Gandalf himself says that the only power Saruman has left is his voice:
['] A snake without fangs may crawl where he will.'
'You may be right,' said Gandalf; 'but this snake had still one tooth left, I think. [Saruman] had the poison of his voice, and I guess that he persuaded you, even you Treebeard, knowing the soft spot in your heart.'
The Return of the King Book 2 Chapter 6: "Many Partings"
It doesn't make a lot of sense for Gandalf to have somehow blocked Saruman from his power. Physically embodied or no, Saruman is still a Maiar; he doesn't do magic, he is magical. The most reasonable explanation is that the power of a Wizard is tied to their staff somehow, although the exact nature of that relationship is unclear.
