In aSoS, Melisandre reveals knowledge of a prophesy, regarding a red star bleeding marking the second coming of Azor Ahai.
Melisandre is heavily associated with the colour red - her eyes, her clothes, her hair, her God - 'the red woman'. She is the embodiment of RED. If Melisandre is the daughter of Shiera Seastar - Star of the Sea, she might be called Melony SeaSTAR. When she sees 'him' (Bloodraven) in her flames, Mel spontaneously starts BLEEDING, overwhelmed by the vision.
It's slightly ambiguous as to what actually triggers the bleeding, but the point is that it could feasibly happen again at the right time and place, with Azor Ahai's rebirth imminent. She would be the RED STAR BLEEDING.
So the most questionable thing here is Mel being Shiera Seastar's daughter. The problem is that we have so little information on Shiera - but we can speculate with what we have got.
Shiera herself can't be Melisandre. It doesn't tally with the scene of Mel in her younger days being called Melony, seemingly a slave. But we can look for links and clues that Shiera and Mel might be related - Melony being the daughter makes the most sense in this scenario (later). We also see a woman cry out Melony Lot7's name when Mel is a lot younger - it would fit that the woman's voice is her mothers.
Shiera was said to have a heart-shaped face, and this description is also given to Mel. A heart-shaped faced is a rare trait, only attributed to two other characters outside of Mel and Shiera, and one of those is related to Shiera. (Mel's possible glamour is explained down-thread btw)
Looking closer at Shiera's description reveals further striking similarities between the two: (credit pobeb)
In comparison to Maester Cressen's description of Mel:
Despite all the undeniable similarities, notice that Melisandre is quite tall, which is not something GRRM says of Shiera. This could be an indicator of Shiera and Mel being closely related rather than the same person. The descriptions we have of Mel make even more sense, and get really interesting, when we compare her with a potential father - Bloodraven (later) - nearly everything about Mel can be attributed to those two.
Shiera had an interest in prophesies, and nobody knows what happened to her. Perhaps she decided to go East, and was captured by slavers and sold on. This would explain why Melony, lot 7, was a slave long ago. Reasons for Shiera fleeing could be; to hide Bloodraven's lovechild from Maekar and others in a turbulent political time or demonisation of royal bastards in the Blackfyre era. Shiera might have tried to head to Lys, given her mother was from there. These scenarios make more sense if she had a secret child or was pregnant.
Tyrion reads three books on the Stinky Steward. The "most engrossing" is about a young slave girl in a Lysene pillow house. It apparently begins with her account of how she and her sister were taken by slavers, which might be a clue.
Mel seems to be very old. She looks young, but thinks of her days "long before Asshai". She needs to look young to be seductive/appear powerful etc., and the fact she seems very old makes a tie-back to D&E era possible. There is a further clue to Mel being older than she seems here;
Mel using magic to disguise her real age links in with Shiera and her Grandmother Serenei, who were both said to use the 'dark arts' to appear younger and possibly live longer. No doubt there might be some rumour involved here, but it could be a link/hint nonetheless. Mel's interest/aptitude with magic generally, might be a likening of personality with Shiera and Serenei - a kind of family trait.
Shiera's necklace - this was a striking characteristic that she was known for, and Mel has a character defining necklace of her own, just with a different jewel. This jewel, a ruby, is heavily associated with House Targaryen, of which Mel would be a blood descendant. The ruby also happens to be described as a RED STAR (later). The fact that Mel wears a gold choker again points to her not being Shiera, as GRRM has said she wouldn't wear gold.
One final observation regarding linking Shiera's necklace to Mel comes courtesy of pobeb; perhaps they like the same colours...
Mel PoV in aDwD:
THE NAME SEASTAR
Regarding the name Seastar. It's worth pointing out that this is more than a random family name. It was given to Shiera and it means 'star of the sea', as if Shiera 'was' a Star. Knowing this, it seems acceptable to describe Shiera or Mel as Stars. Why did GRRM tell us that Seastar meant 'star of the sea', and used the phrase interchangably? It's also such a curiously unique and standout name.
There are two occasions on which Mel (and necklace) are described as being like a red star. This could be a further hint, and no other character is given this red star association.
There is also an instance of Shiera being sneakily linked with the red star bleeding, courtesy of the Dothraki's word for 'bleeding star'...
The only other mention of Shiera in the five books says that the Kingdoms 'bled' for her. Again, I'd argue that these are part of a clue trail leading us to Mel being the red star, rather than Shiera herself.
If we consider that the name (and the other clues) might make Mel a 'red star', all that's needed is for her to bleed at he right time and place. Given she bleeds in such a strange and standout manor in her POV, with no physical cause, it's not difficult to imagine it happening again (perhaps with certain triggers), which would make her the RED STAR BLEEDING.
And if the prophesy is correct, when the red star bleeds - Azor Ahai will be reborn.
Some associated thoughts below, I'll use spoilers to less confuse the thread... (don't miss this Bloodraven one, it really ties in)
BLOODRAVEN AS THE FATHER
PART 2 is here and concerns the manor in which the red star might bleed.
Thanks to Dr Pepper, pobeb & Lost Melnibonean for a 'lil help