The prince that was promised
The prince that was promised is a prophesied leader or savior. The prince may be part of an ancient prophecy, a prophecy that foretells the coming of a hero to deliver the world from darkness. A "bleeding star" is supposed to herald the coming of the prince.
At the moment it is not known where the prophecy originates, information on the prince that was promised is rather scant. Based on the fact that Maester Aemon mentions “a thousand years”  to Samwell Tarly it should be safe to say the prince that was promised prophecy is a thousand years old.
It appears as if the Targaryen family had been awaiting the arrival of the prince so the prophecy may come from Old Valyria - but that is conjecture. There is not as much clear information on the prince as, for example, Azor Ahai.
Thus far there has been no mention of the prince wielding a sword - unlike the last hero and Azor Ahai. However at one point Prince Rhaegar Targaryen believed that he might be the prince that was promised. According to a tale told of Rhaegar one day he found something in his scrolls that changed him and he decided to become a knight. He said to Ser Willem Darry, the master-at-arms,
I will require a sword and armor. It seems I must be a warrior.
Therefore, the prince may be a warrior who wields a sword.
“When the red star bleeds and the darkness gathers, Azor Ahai shall be born again amidst smoke and salt.
Much later in Braavos, when talking of the prince to Samwell Tarly Maester Aemon mentions smoke and salt as being part of the heralding of the prince that was promised coming. Obviously the mention of smoke and salt immediately brings to mind Melisandre’s above mentioned statement. However it is important to keep in mind what Tyrion Lannister has stated about prophecy,
Therefore, readers have to be careful of being kicked in the head by smoke and salt also being mentioned in relation to the prince that was promised. Azor Ahai and the prince that was promised may be two distinct prophecies, or they may be one in the same in a prophecy that has the potential to turn out to be about two separate people. It is easy get rather confused. Indeed the prince may not even be male; the prince may have been referred to as male erroneously for centuries. Before his death Maester Aemon came to firmly believe that the prince is not a prince but a princess.
Maester Aemon also says to Samwell that the dragon must have three heads. He wakes up weeping, wailing:
It may be that the three-headed dragon is a part of the prince that was promised prophecy, and there are two other people whom the prince will need to have by his side, to show him the way.
Signs of the coming of the prince that was promised
- The birth of a male child - a prince. (erroneous according to Maester Aemon) 
- The prince is of the blood of the dragon. 
- Born amidst smoke.  
- Born amidst salt.  
- A bleeding star in the skies.  (also mentioned is being born beneath a bleeding star) 
- The return of dragons? (when he was a boy Aegon V recalled that King Aerys read about the return of dragons in a prophecy.) 
- The dark eye falls upon the prince?
The prince that was promised theories
A Clash of Kings
Daenerys Targaryen’s elder brother Prince Rhaegar appears in one of her visions in the House of the Undying in Qarth. She sees him talking to his wife Elia discussing what he shall name his son (Aegon) and his destiny. He states,
He looks up when he says those words and his eyes meet Dany’s, though whether he is speaking to her or the woman in the bed she cannot say.
Later, when down at the port of Qarth with Ser Jorah Mormont she discusses the vision with him. She mentions her brother said that the babe was the prince that was promised. Jorah observes that if he was this prince that was promised, the promise was broken along with his skull when the Lannisters dashed his head against a wall. Dany seems to accept this notion and goes on to ask what is the song of ice and fire but Jorah has never heard it. 
A Storm of Swords
Maester Aemon replies:
It is the war for the dawn you speak of, my lady. But where is the prince that was promised?
A Feast for Crows
In Braavos, after Samwell Tarly tells Maester Aemon of the rumors about Daenerys Targaryen and her dragons, Aemon becomes convinced that Daenerys is the prophesied leader.  Maester Aemon states to Sam,
A Dance with Dragons
Ser Barristan Selmy talks to Dany about her mother and father. He mentions that her grandsire commanded that they be wed after a woods witch had foretold that the prince who was promised would be born of their line.  Dany is astonished by the fact that her grandsire listened to a woods witch and asks Ser Barristan about her, when Barristan mentions Summerhall she sighs and tells him to leave. Dany never asks him about the prince who was promised or makes mention of her vision in the House of the Undying to Ser Barristan.
References and Notes
- A Feast for Crows, Chapter 35, Samwell IV.
- A Clash of Kings, Chapter 48, Daenerys IV.
- A Dance with Dragons, Chapter 40, Tyrion IX, page 534.
- A Feast for Crows, Chapter 45, Samwell V.
- The Mystery Knight, Warriors 1, ISBN 978-0-7653-6026-7, page 282 of 251-394.
- A Clash of Kings, Chapter 63, Daenerys V.
- A Storm of Swords, Chapter 78, Samwell V.
- A Dance with Dragons, Chapter 23, Daenerys IV.