We know from the movies that Palpatine was a senator from Naboo when he began his rapid rise to power in the Republic, but what's his back story? How did Palpatine become an apprentice of the Dark Side? Who was his master? And how did he become so powerful without the Jedi knowing until he and Maul revealed themselves in Episode I?
Note: all this refers to Legends canon. Pre-Episode III EU material is more likely to be integrated into the Disney canon, but as of now, it is not official canon. We don't see any official word in the films about Palpatine's rise as a Sith other than what Jeremy Cox noted in his answer. It is possible that the upcoming canon novel Lords of the Sith will provide some backstory on Palpatine.
Palpatine was originally from Naboo, the planet he is shown to represent in the Galactic Senate in The Phantom Menace. As told in the novel Darth Plagueis, Palpatine from an early age was ambitious, and soon began searching out knowledge of the Sith, apparently on his own. After years in secret searching out artifacts and studying how to rise to power on Naboo, Palpatine released secret information that cast discredit on many powerful families on Naboo. This incident brought attention to himself from Hego Damask, who was in secret Darth Plagueis, Sith Lord in search of an apprentice.
During the first time Palpatine met Plagueis, he eventually admitted his dissatisfaction with those in power.
Plagueis came to a stop in the middle of the walkway. "How deep does your interest go? To what position do you aspire? Republic Senator? Monarch of Naboo? Supreme Chancellor of the Republic?"
Palpatine glanced at him. "You'll think less of me if I tell you."
"Now you underestimate me, as you do your father."
Palpatine took a deep breath and continued. "I want to be a force for change." His look hardened. "I want to rule."
There! Plagueis thought. He admits it! And who better than a human to wear the mask of power while an immortal Sith Lord rules in secret!
"If that can't happen, if you can't rule, then what?"
Palpatine ground his teeth. "If not power, then nothing."
Plagueis smiled. "Suppose I said that I would be willing to be your ally in the quest." (Darth Plagueis, p. 134-135)
And with that, their involvement together began and grew. Later, when Palpatine's hated father found out about their close involvement, he confronted Palpatine and Palpatine murdered his father, the rest of his family, and the guards using the dark side. He then contacted Plagueis, who formally apprenticed him in the Sith order as his apprentice, Darth Sidious.
Over the next many years, Sidious' power grew under Plagueis. Careful to keep a low profile, and trained by Plagueis to avoid detection from the Jedi, they eventually decided to move more openly, and manipulated his way into being the Senator of Naboo. From then, the two Sith worked together for years, training and politically manipulating to build power until shortly after Palpatine's election to chancellorship, Palpatine
murdered Plagueis in his sleep and assumed to mantle as Lord of the Sith.
Palpatine's Master was likely Darth Plagueis. Palpatine tells the story of Darth Plagueis to Anakin in the films, where Darth Plagueis is purported to have created Anakin -- his studies of the Force gave him to ability to create life (Anakin's divine conception.) It is implied that Darth Plagueis could not foresee his own death, Palpatine is referring to his betrayal and killing of Plagueis.
Regrettably my Star Wars fu is not as strong as it once was, I cannot tell you 100% that this is the way it is.
Darth Plagueis' story is now available in a book by the same name.
It is established in Star Wars canon that the Sith Lords, after they lost a great Jedi - Sith war, they were severly outnumbered and discovered a way to hide themselves in the force, so the Jedi could not detect them and wipe them out.
This goes back to the idea that the Force is neither good nor evil, but perhaps a neutral force looking to maintain a balance of sorts. The legend of Anakin's birth to "bring balance to the force" may perhaps refer to destroying the Jedi who were strongly tipping the scales out of favor towards good.
Palpatine was from Naboo, and soon came in contact with Plagueis, whose identity was unknown then. Eventually, Plagueis made Palpatine his apprentice, and the two went through so much together that Plagueis did not see his pupil's betrayal coming. Eventually, Palpatine rose to power in the Senate, and manipulated the Clone Wars, putting Plagueis' plan into effect.
Essentially, it is rumored that Plagueis may have manipulated the force into creating a force user so strong, he could tip the scales: Anakin Skywalker. There is never a mention of Anakin's father, only his mother, so Anakin may indeed be a force-child, the only of his kind. However, Plagueis never managed to advance his plan further, as Palpatine killed him and took his place.
Palpatine then fabricated conflict, which grew into the Clone Wars, in order to manipulate Anakin away from the Jedi, bit by bit. Palpatine's patience and forethought is astonishing here. He purposefully revealed himself to Anakin, knowing that Anakin would go to Windu, then later come himself. Windu is manipulated by Palpatine into trying to kill him, forcing Anakin to intervene, since Palpatine had made sure to form a bond with Anakin beforehand.
Palpatine only took Maul and Dooku as his apprentices in order to advance his plan, revolving around Anakin. Once they outlived their usefulness, he set certain wheels in motion in order to get rid of them so his plan remained a secret.