How did Melisandre know about Gendry's whereabouts?

Question

During Game of Thrones S03E06 "The Climb" the red witch priestess Melisandre comes to the secret hideout of the Brotherhood Without Banners in order to take Gendry the blacksmith (and bastard of Robert Baratheon) with her, much to Arya's dismay.

However, given that it is such a secret hideout and Gendry ending up there was merely a coincidence and nobody seemed to know who he is at all, how did she even know where he is, let alone who he is? Did she have any kind of connection to the Brotherhood (seeing that they were also believing in the "Lord of Light") or are we to assume that all her knowledge came merely by the help of the "Lord of Light"? Or is there any other explanation that maybe didn't make it from the books to the TV show (or just not from the TV show to my attention)?

Answer 1

By this point, I believe R'hllor (The Lord of Light) does exist. Based on:

• Melisandre giving birth to an evil shadow baby which murders Renley in Garden of Bones/The Ghost of Harrenhal
• Beric Dondarrion's repeated resurrection by Thoros of Myr in Kissed By Fire

This, combined with the fact that neither Thoros nor Beric were expecting to see her when she arrived at their cave in The Climb, there's no explanation for how she knew this other than it being information divined from the fire, as she does several times (such as when the letter from The Night's Watch arrives).

And as Will Feldman mentioned in the comments, in the book it was actually Edric Storm who was used in this role, and it's common knowledge that Edric Storm is in Storm's End before Melisandre even meets Stannis, so as this was an original idea to the show, there's no explanation from there either.

Answer 2

She was sent there by the Lord of Light of himself.

In the same episode and scene you mention, when Melisandre meets with Thoros and Beric they have an exchange (at about 5:44 in the linked video)

Beric: He sent you to us for a reason.

Melisandre: You have someone he needs.

We do need to do a little extrapolation/assumption, but as seen in other places, Melisandre communicated with R'hollor through the flames. I see no reason why this was any different.