We have seen Lady Melisandre in season 2 of Game of Thrones with Stannis Baratheon, but who is she? How did she meet Stannis?
This wasn't explained in the show (apart from the fact that she has been a slave), the information we have comes from the books.
From GoT Wiki:
In the A Song of Ice and Fire novels, Melisandre is a priestess of the red god, R'hllor, the Lord of Light, whose worship involves the idolization of fire and light. R'hllor is a popular deity in several of the Free Cities (particularly Lys, Myr, and Volantis) but is almost unheard of in Westeros. Although the series has altered some of Melisandre's actions, van Houten's portrayal is overall consistent with Melisandre as described in the books.
Very little has been revealed about Melisandre's earlier life, other than that she is originally from the city of Asshai in the distant east. Melisandre recalls that as a small child, she was a slave named "Melony". At the slave auction block, she was known as "Lot Seven". She was sold at a young age to the temple of the Lord of Light in Asshai, eventually rising to become a priestess, and thus has spent most of her life in the service of the religion.
Some years ago she crossed the Narrow Sea and came to the court of Lord Stannis Baratheon on the island stronghold of Dragonstone, to preach her faith. Stannis and the majority of his household have now converted to her religion, and she has become a close adviser to Stannis himself.
From the books wiki:
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. (...) Melisandre proclaims Stannis Azor Ahai reborn and has him pull a burning sword from the idols, declaring it to be the legendary Lightbringer.