Why did Melisandre travel to Stannis?
As the author says (Tip of the hat to Prakhar Mishra):
Why did Melisandre seek out Stannis? Did she see him in her flames and
decided to seek him out on her own, or is she on a mission on behalf
of the red priests? It doesn't seem at any point as if the latter is
the case, when you compare to Moqorro who has been sent out by the
priesthood.
You're right. Melisandre has gone to Stannis entirely on her own,
and has her own agenda.
So now we have established that Melisandre came to Stannis entirely on her own presumably after reading the signs which she thought meant that Stannis was Azor Ahai Reborn.
But in universe, The Lannisters believed it was Stannis who hired the woman, as per Varys' reports.
His father frowned. "I have felt from the beginning that Stannis was a
greater danger than all the others combined. Yet he does nothing. Oh,
Varys hears his whispers. Stannis is building ships, Stannis is
hiring sellswords, Stannis is bringing a shadowbinder from Asshai.
What does it mean? Is any of it true?" He gave an irritated shrug.
"Kevan, bring us the map."
AGOT - Tyrion IX
However, note that Tywin appears to be skeptical of that.
How did she get access to inner circles of Stannis Baratheon?
Now that we have reviewed how Melisandre came, let's see how did she get close to Stannis.
As we know Stannis was notoriously uneasy around women, even (Or especially) his own wife. So how he came to be close to Melisandre is indeed curious.
She didn't get close to Stannis immediately. She had to work her way up through his wife.
It took her some time to become a confidant of Selyse Florent and to convert her.
Pycelle cleared his throat. "These words often appear in letters and
documents from the Free Cities. They mean no more than, let us say,
written in the sight of god. The god of the red priests. It is their
usage, I do believe." "Varys told us some years past that Lady
Selyse had taken up with a red priest," Littlefinger reminded them.
Tyrion tapped the paper. "And now it would seem her lord husband has
done the same. We can use that against him. Urge the High Septon to
reveal how Stannis has turned against the gods as well as his rightful
king . . ."
ACOK- Tyrion III
Why did Stannis listen to her?
But it was Stannis himself who started listening to the Red Woman with big promises, simply because, what did he have to lose? All the acts which lead to him actually believing in her came later.
"I trusted in his wisdom and your wiles, and what did they avail me,
smuggler? The storm lords sent you packing. I went to them a beggar
and they laughed at me. Well, there will be no more begging, and no
more laughing either. The Iron Throne is mine by rights, but how am
I to take it? There are four kings in the realm, and three of them
have more men and more gold than I do. I have ships . . . and I have
her. The red woman. Half my knights are afraid even to say her name,
did you know? If she can do nothing else, a sorceress who can
inspire such dread in grown men is not to be despised. A frightened
man is a beaten man. And perhaps she can do more. I mean to find
out.
"When I was a lad I found an injured goshawk and nursed her back to
health. Proudwing, I named her. She would perch on my shoulder and
flutter from room to room after me and take food from my hand, but she
would not soar. Time and again I would take her hawking, but she never
flew higher than the treetops. Robert called her Weakwing. He owned a
gyrfalcon named Thunderclap who never missed her strike. One day our
great-uncle Ser Harbert told me to try a different bird. I was making
a fool of myself with Proudwing, he said, and he was right." Stannis
Baratheon turned away from the window, and the ghosts who moved upon
the southern sea. "The Seven have never brought me so much as a
sparrow. It is time I tried another hawk, Davos. A red hawk."
ACOK- Davos I
So at this point:
- Stannis was skeptical of her magical powers.
- Stannis didn't have anything to lose by trusting her. He didn't have any better option anyways.
- Stannis thought even if she couldn't do any magic, she was still useful as his men feared her.
- Stannis is a self-confessed atheist, in reality. He didn't care about pretending to take up another god if it gave him what was his.
Okay whatever, what was the first act?
Her first actual act was giving Stannis "Lightbringer" but as Stannis himself noted, while the sword glimmered prettily, it didn't serve him any better than any other sword.
"We do not choose our destinies. Yet we must . . . we must do our
duty, no? Great or small, we must do our duty. Melisandre swears that
she has seen me in her flames, facing the dark with Lightbringer
raised on high. Lightbringer!" Stannis gave a derisive snort.
"It glimmers prettily, I'll grant you, but on the Blackwater this
magic sword served me no better than any common steel. A dragon
would have turned that battle. Aegon once stood here as I do, looking
down on this table. Do you think we would name him Aegon the Conqueror
today if he had not had dragons?"
ASOS- Davos V
But we have to note, that was after Stannis got defeated in Battle of Blackwater Bay. Before that, he didn't voice any objections to the sword in public.
Then there was Renly's murder at hands of a shadow baby. Stannis struggled to deal with it, reiterating that his own hands were clean. But that made Stannis a believer, He trusted what She said next:
Davos Seaworth felt the small hairs rising on the back of his neck.
"My lord, I do not understand you."
"I do not require your understanding. Only your service. Ser Cortnay
will be dead within the day. Melisandre has seen it in the flames of
the future. His death and the manner of it. He will not die in
knightly combat, needless to say." Stannis held out his cup, and
Devan filled it again from the flagon. "Her flames do not lie. She
saw Renly's doom as well. On Dragonstone she saw it, and told Selyse.
Lord Velaryon and your friend Salladhor Saan would have had me sail
against Joffrey, but Melisandre told me that if I went to Storm's
End, I would win the best part of my brother's power, and she was
right."
ACOK- Davos II
So as evident, after Renly's death, Stannis started believing her powers and the truth of her flames.
