Ela foi enviada para lá pelo Senhor da Luz de si mesmo.
No S3E6, quando Melisandre se encontra com Thoros e Beric eles têm uma troca (por volta das 5:44 no vídeo vinculado )
Beric: He sent you to us for a reason.
Melisandre: You have someone he needs.
Precisamos fazer um pouco de extrapolação / suposição, mas como visto em outros lugares, Melisandre se comunicou com R'hollor através das chamas. Não vejo razão para que isso seja diferente.