Just as the question asks: Why did Anakin come to believe that Padmé could be saved if he embraced the Dark side of the Force? Padmé clearly didn't believe it. Why was Anakin so driven to save Padmé through the dark side?
When he first looked for advice from Yoda about his vision, he did not hear what he wanted to hear. From Star Wars Episode 3 Revenge of the Sith Script
YODA: Careful you must be when sensing the future, Anakin. The fear of loss is a path to the dark side.
ANAKIN: I won't let these visions come true, Master Yoda.
YODA: Death is a natural part of life. Rejoice for those around you who transform into the Force. Mourn them, do not. Miss them, do not. Attachment leads to jealousy. The shadow of greed, that is.
ANAKIN: What must I do, Master Yoda?
YODA: Train yourself to let go of everything you fear to lose.
But later, Palpatine told him about a possible way to save her :
PALPATINE: I thought not. It's not a story the Jedi would tell you. It's a Sith legend. Darth Plagueis was a Dark Lord of the Sith, so powerful and so wise he could use the Force to influence the midi-chlorians to create life ... He had such a knowledge of the dark side that he could even keep the ones he cared about from dying.
ANAKIN: He could actually save people from death?
PALPATINE: The dark side of the Force is a pathway to many abilities some consider to be unnatural.
So, Anakin's dilemma was that Yoda told him he must accept Padmé's death and Palpatine told him he could avoid it by turning to the Dark Side.
Palpatine also told him that the Dark Side is not Evil as the Jedi told him and made him doubt the real intention of the Jedi order, that they where hanging on power and that their actions where not always for the greater good. In the end, Anakin turned to the Dark Side to save Padmé, but also because he had some conflict of opinion with the order. He was convinced that he was doing the right thing.
Because Chancellor Palpatine convinced and intrigued Anakin's hopes that only the Dark side of the force had the power to cheat death with a tale of "the tragedy of Darth Plagueis The Wise".
This was further concluded in Anakin's mind after he succumbed to the dark side and Lord Sidious remarked
To cheat death is a power only one has achieved, but if we work together, I know we can discover the secret.
As a side note, in turning to the dark side Anakin actually lead to Padme's death but what Palpatine actually told Anakin was true from a certain point of view.
DavRob60's answer only addresses part of Anakin's motivation. Anakin chose the dark side to save Padmé. The central question is why Anakin chose to save Padmé versus letting go of her.
Anakin started his Jedi training too late. He had already developed an attachment to his mother and that served as the model for his attachment to Padmé.
These were the exact fears expressed by the Jedi council when he first went before them and it is the same reason that Yoda was reluctant to train Luke. It could be argued that Luke didn't have the same level of attachment to his aunt and uncle and after their death he had none whatsoever.
When Anakin tried to follow the Light side by initially ignoring his prophetic dreams about his mother, the end result was that he got there too late to save her. When he started to have similar dreams about Padmé, and especially when he was unable to foresee the fate of his child, he became fully susceptible to Sidious/Palpatine's stories about Force powers that could cheat death.
He had dreams about his mother being in trouble in Attack of the Clones and because he felt his mother's agony Anakin left to find where Shmi was. He found her eventually but he was too late to save her as the Tusken raiders did too much damage.
In Return of the Sith Anakin had similar dreams to Shmi's where Padmé was dying in childbirth, this led to Anakin thinking it would come true like his mother's. This wasn't the case at all. So he went on a mission to try and find ways to save Padmé and also help.
He met Yoda who said "To train yourself to let go of everything you fear to lose," which meant accepting Padmé's death. He was given orders to spy on Chancellor Palpatine's dealings but when he met him the first time the Chancellor basically described the Dark Side to Anakin including how it can save the ones you love - "it's a pathway to many abilities that some consider unnatural".
As Anakin believed the Chancellor he put some deep thought about what to do. As Anakin's trust in the Jedi order was at a very low ebb, because he wasn't allowed to be a Jedi Master, he eventually came to Palpantine's aid when Mace Windu was about to kill him. Anakin was stuck in two minds before deciding to stop Windu from killing Palpatine, which caused Windu's demise instead.
Believing Palpatine, Anakin decided to turn to the Dark Side. I think Anakin never would have listened to Padmé, and Obi-Wan's arrival topped off his hatred. Anakin turned to the Dark Side because he was too attached to the ones he loved and couldn't let go of them, and he thought the Jedi never trusted him.
I feel sorry for him because he was made out to be the bad guy when really he is the victim because he was trained too late and his mind was fucked from then on. :)
And then from there Padmé tried to stop him by meeting him in Mustufar which resulted in Anakin choking Padmé as he thought Obi Wan and her were trying to kill him. I think Anakin was never going to listen to Padmé as he knew these dreams would come true (they weren't). So Anakin turned to the Dark Side because he was to attached to her.
I think in Episode 2 you can already see what was about to happen when Anakin tried to save his mother, but had to accept that it was already too late. He never accepted that fact, and besides killing the sand people, the funeral scene on Tatooine is a key scene for the Star Wars Saga with the old man (Cliegg Lars) is mourning, but accepting the death of the woman he loves.
Young Anakin, in contrast, is staring at the grave with a hardened face, where you can see that he is fighting with his feelings of guilt. The story is well thought out, and many things accumulate until the scene where Anakin finally cuts off Mace Windu's hand and intentionally turns to the teachings of Darth Sidious.
To Anakin, the light side of The Force has proven to be inferior and weak in many events, especially because most of his "career" is spent in a time of war, where being "good" most of the time turns out to be on the losing side.
Wartime trains people to use their "dark side". This is true in our society as well. From that perspective, someone like Obi Wan even seems unrealistically moral and humane, given the circumstances. The process that changes Anakin seems to me as the more logical course a person, especially a "war hero" will go in a story like this.
Granted, the final scene when he turns to Darth Sidious just after he turned him in, is all too stereotypical, but everything that leads up to it seems quite conclusive...