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?
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.