I just started reading book 2, a Clash of Kings, where "Melisandre" is introduced right in the first chapter. I guess that means we'll be seeing Carice van Houten in the very first episode of the 2nd season.
"Stannis will be played by British actor Stephen Dillane, best known to U.S. audiences by playing Thomas Jefferson in HBO’s John Adams.
Stannis Baratheon is the late King Robert’s younger brother who makes a claim for the Iron Throne based on the assertion that Joffrey is not Robert’s son. Melisandre is a mysterious priestess and sorceress from the distant lands of Asshai who aids Stannis in his push for the throne."
(Spoilered for gigantic wallpaper picture of Melisandre.)
Right at the start of the 2nd book, Melisandre is established as a menacing but beautiful woman, with mysterious powers. Carice van Houten seems like a perfect match. I heard there was initially talk of her perhaps playing the part of Cersei as well.