This relates to the very touching story of Proudwing, as Stannis relates it to Davos.
"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."
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."
—George R.R. Martin, A Clash of Kings, Davos I (Chapter 10)
From the wikipedia:
Melisandre came to Dragonstone because she believed Stannis Baratheon
is Azor Ahai reborn and destined to defeat the Great Other the
antithesis of her god. She turns Stannis' wife, Lady Selyse Florent,
and several other members of Stannis’s court from the Faith of the
Seven to her red god.
In some not quite disclosed way, she demonstrates her power to Stannis, which convinces him that it is time to "try a different bird": R'hllor. Stannis recognizes Melisandre's power, but is not a devout believer of her faith. Nor have I ever seen him express any faith in any other god. In this, I believe Stannis is entirely pragmatic.