Basically, this is an attempt to explain just what was going on in the background of the first three movies and especially Episode One.
Having now seen ROTS and seen information from the various prequel adaptations and the corresponding Visual Dictionaries, I think there's enough hints to piece together a relatively 'tight' speculatory origin of Senator/Chancellor/Emperor Palpatine.
We know that Amidala's predecessor to the Naboo Throne was King Veruna. He was the one who appointed Palpatine to the Galactic Senate.
Veruna resigned from office after a mass grave was discovered near Theed. There was evidence pointing to him, though what that evidence was has not been disclosed. It was also hinted that something there may have pointed to Palpatine as well, but Veruna's chief of security, Captain Magneta's lieutenant, Panaka, sealed the site before the investigation could be completed.
We also know that Veruna was killed in his sleep after he resigned in disgrace, and Magneta abdicated his position to Panaka. Sio Bibble was the favorite to replace Veruna, until Palpatine threw his support behind the then Governor of Theed, a young girl named Padme.
So, it is my contention that, based on the 'Tragedy of Darth Plagueis' story that Plapatine tells Anakin, Darth Plagueis was indeed, King Veruna. He trained his apprentice, Palpatine/Sidious, not only in the Dark Side of the Force, but also in Politics. Veruna ruled over Naboo, while Palpatine went to the Senate.
We know that both Veruna and Plagueis were killed in their sleep.
We also know that Shmi Skywalker and her son Anakin were not always slaves on Tatooine. They were sold to Gardulla the Hutt, who then sold them to Watto (or lost them in a bet).
Plagueis meddled with life and death. I theorize that the mass grave found on Naboo, more than likely 'revealed' by Palpatine as he exacted his betrayal on Veruna, were the precursors to their first successful Force Conception, Shmi Skywalker. Once Shmi became pregnant, Veruna/Plagueis and Palpatine/Sidious sold her into slavery.
Anakin was put into slavery as a way of putting him into hiding until the time was right. Also, Darth Maul was probably already a Sith apprentice by then, so Palpatine wouldn't need the boy right away, especially without the knowledge he would be so strong in the Force. Plus, what better way then to have him slave away in the Outer Rim and Hutt territories? Anywhere else and the Jedi would have discovered his extremely high mid-chlorian count, as seen in the conversation between Shmi & Qui-Gon in TPM, and would have taken him into Jedi training at a very early age. Which of course would lose him forever for the Sith.
Also you would test Anakin in the hardest way possible. A slave, who had nothing, was nothing but a piece of property will probably ultimately give into the temptation of unlimited power, respect and authority more so than a child of privilege.
Panaka, we know from the Visual Dictionaries, had been feeding Palpatine information on Padme. This indicates that he still holds loyal to the Chancellor. We also know that SOMEONE sold them out to the Sith in The Phantom Menace. I beleive that was Panaka.
When Obi Wan suggests Tatooine as a landing site, Panaka tries to keep them away. His excuse is that it's dangerous for the Queen. However, once they land, he is eager to get Qui Gon to take Padme, in her handmaiden guise into the city with them. Why? To keep them on task. We see Padme try to keep Qui Gon focused on getting the ship repaired. If Panaka knew that Sidious' force-child was on Tatooine, it would be imperative to keep Qui-Gon away from him.
Enter Darth Maul. If Maul's objective was to bring the Queen back to Naboo, why go after Qui Gon? Amidala was relatively unguarded on her ship, only a handful of under-armed Naboo security guards, 3 handmaidens and a Padawan. Yet Maul went after the Jedi Master. Again, ask yourself why? Qui Gon had no bearing on the plan, he was a wild card to either be eliminated now or later. What he did have, was Anakin.
There's also many who swear up and down that the Sith Probe Droid who reports to Maul chirps: "The Boy, The Boy!" However, remember just who Maul tried to run over with his speeder bike: Anakin.
If not for Qui Gon screaming to Anakin to drop, we have a very headless little Chosen One. So why would Maul do that? The answer is simple, Maul wanted Anakin out of the way. He felt Anakin was a threat to his contention of being a Sith Lord Master.
There was always only two Sith; no more, no less, a master and an apprentice. Maul figured if Sidious learned Anakin was alive then his spot as a Sith apprentice was in jepardy. So he tried not once but twice to kill Anakin, (the speeder bike and also the Destroyer Droids popping out from the back in the Theed palace).
Plus it would also explain why Maul was so methodical in his duel with Qui-Gon and Obi-Wan. Kill the Jedi Master, Qui-Gon, thus Anakin couldn't be trained in the Jedi arts. No Padawan could ever teach him anything. Hence why Maul was torturing Obi-Wan instead of going for the kill when he had the advantage. He honestly thought probably he won the duel and secured his position again.
So he attempted to kill Anakin, but failed both times and died.
Though unfortunately for Maul, somehow I think Sidious found out, (probably through Panaka) and then sent Maul to "assist" the Trade Feds on Naboo. Why? Anakin's alive, so why bother with a troublesome apprentice who was beginning to think too much.
Sidious decided to change his priorities on making Anakin his apprentice. Plus it would be hard for Sidious to fool Maul since Maul probably knew all about Sidious's late master. Notice at the end, the moment Palpatine walks out he goes straight to Obi-Wan and Anakin.
So Palpatine then locates Dooku, who he probably only gave some training to. To Palpatine, Dooku was nothing more then just a test to see Anakin's full power and a way to make the Jedi think Dooku was the big bad Sith Lord they were searching for.
After all, if Dooku was a full Sith Lord, why didn't he have the whole yellow eye thing like Sidious, Maul, and Vader? Plus Dooku's style of fighting was very calm compared to the brutality of the other trio's style of saber. Even when he fought Anakin in the final duel or Yoda in AoTC, Dooku's style was still calm and collected, not wild and physical.
Poor Dooku was just a big pawn in Sidious's plan to test Anakin. The way Christopher Lee brilliantly acted Dooku's look to Palpatine just before Anakin killed him was just a perfect look of realizing how much a guided sheep he was in the grand scheme of things.
Interestingly, according to Wikipeida's entry on Naboo, Panaka ended up as an Imperial Moff. That information apparently came via Star Wars Galaxies, so take it with a pinch of salt. But it does support the theory nicely.
Other sources : the Star Wars Visual Dictionaries, the Making of Books, and the Art of books.
Abstracted from a number of posts on Newsarama, and pieced together. Sorta makes you want to watch Episode One all over again, huh?