In season 3 of Game of Thrones, Melisandre the "Red Woman" exchanges Gendry by paying lots of gold to the Brotherhood Without Banners. Later, she reveals that Gendry has royal blood as he is Robert's son. Very few people were aware of this fact and he was one of very less known bastards. Even he himself was not aware. So how did she know that?
2she can smell it– DForck42Dec 8, 2016 at 14:53
2In the books it was a different character who was well-known to be Robert's bastard and boasted about it, and I don't think anything in the show addresses this directly, so I think the answer is probably a disappointing "We don't know, maybe she saw him in the flames or something". At a stretch, in the books it's mentioned that Jon Arryn was in close communication with Stannis about his investigations, so maybe you could say Jon told Stannis that Gendry was a dark-haired Baratheon bastard, and Stannis told Mel? But I think in the show, Stannis was 100% surprised about Robert's kids...– user56reinstatemonica8Dec 8, 2016 at 15:01
She was sent there by the Lord of Light of himself.
In S3E6, 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 would any different.