Spoilers from Season 6 of Game of Thrones, potentially impacting on events in the unpublished Song of Ice and Fire novels, ahead.
In science fiction and fantasy novels, the largest such mystery for many years was in the Wheel of Time novels by Robert Jordan. In the fifth novel in the series, The Fires of Heaven (published in 1993), a character named Asmodean is killed by persons unknown. Jordan declined to reveal who was responsible. The years and books ticked by and Jordan encouraged fan speculation. Of course, he knew who had done it: a member of the Forsaken who would show up at the start of the next book in disguise. Unfortunately, fans saw through that almost immediately and Jordan rethought both the identity of the killer and in fact the whole disguise storyline. In the early 2000s he stumbled across an extremely long fan theory online about the identity of the killer and printed it out, writing, "This is it," in the margin. This theory made it into canon in the penultimate novel of the series, Towers of Midnight, which was published in 2010, seventeen years after the mystery was first mooted (and three years after Jordan's own passing).
However, its status as the biggest mystery in fantasy had already long been supplanted. In 1996 George R.R. Martin published the first novel in A Song of Ice and Fire, A Game of Thrones. A minor subplot revolves around the status of Eddard Stark's bastard son, Jon Snow, born out of wedlock to Eddard and...well, someone. His wife, Catelyn, believes it was a Dornish noblewoman, Ashara Dayne of Starfall. Eddard himself has told King Robert Baratheon - incredibly reluctantly - that it was a serving girl named Wylla. In A Storm of Swords the young lord of Starfall, Edric Dayne, also confirms (to Arya Stark) that it was Wylla, who was his wetnurse.
But fans felt this was a little too neat. Eddard's rigid honour and honesty is taken as a point of overwhelming fact throughout the books. It even, ultimately, gets him killed. Would a man whose honour resulted in him getting his head chopped off really dishonour his intended bride, his name and his house all in one swoop? It seems unlikely, although not impossible. It was, after all, a war that Eddard's side seemed certain to lose and it is easy to imagine, under the threat of likely death, Eddard slipped up in a moment of passion.
There are also two chapters, one in each of the first two books, that hint at a different turn of events. Throughout A Game of Thrones Eddard remembers his sister Lyanna dying in the "Tower of Joy", a towerhouse on the Dornish Marches where Prince Rhaegar Targaryen had taken Lyanna. Robert's Rebellion - the War of the Usurper - began with Rhaegar's "abduction" of Lyanna after the great tourney at Harrenhal in the Year of False Spring. Eddard's older brother, Brandon, accused Rhaegar of kidnapping and rape and was executed by the Mad King for it, along with their father. Eddard became Lord of Winterfell, raised his banners and joined Jon Arryn, Hoster Tully and Robert Baratheon in defeating the Mad King.
But no-one apart from the late Brandon and Robert seem to really believe that Rhaegar abducted Lyanna against her will. Lyanna was a formidable rider and a surprisingly effective fighter. She was also clearly besotted with Rhaegar at the tourney, and Rhaegar apparently returned the feelings, naming her Queen of Love and Beauty over his own wife, Elia Martell of Dorne. Although rash and precipitous, Lyanna absconding with Rhaegar was not out of character. The resulting conflict can be laid more at the Mad King's execution of Brandon and Rickard and his demand for the heads of Eddard and Robert more than Rhaegar's actual actions. If Rhaegar and Elia had come forward and admitted that the "abduction" was mutual, there would have been embarrassments, restitutions and apologies, but actual bloodshed on the scale we saw in the rebellion was unlikely. The resentment of the Mad King's growing brutality over the preceding years and his own insanity blew the matter out of all proportion.
Rhaegar Targaryen, Prince of Dragonstone, born in 259 AC on the night of the infamous great fire of Summerhall which claimed the life of his great-grandfather. Son and heir to the Mad King, slain by Robert Baratheon at the Battle of the Trident in 283 AC. The father of Rhaenys and Aegon Targaryen by Elia Martell and of Jon Snow by Lyanna Stark.
In the Tower of Joy, weeks after Rhaegar's own death at Robert Baratheon's hands in the Battle of the Trident, Eddard found his sister dying in a "bed of blood". She repeatedly asked him, "Promise ne, Ned!" but we never found out what he promised. But even first-time readers in 1996 rather easily found the answer: Jon Snow is the son of Lyanna Stark and Rhaegar Targaryen, and Lyanna beseeched Eddard to raise Jon as his own, as she knew Robert would kill the child if there was even a hint of him knowing the truth (as he had just been proven in the Sack of King's Landing, when he approved Tywin Lannister's "execution" of Aegon and Rhaenys Targaryen, along with their mother Elia Martell).
Eddard not only agreed, but called upon his already-known friendship with Ashara Dayne (also forged at the Harrenhal tourney) to give the story credence, as well as then complicating the story with rumours of a dalliance instead with Ashara's maid, Wylla, and with a fishing girl from the Vale when he was trying to get back to Winterfell at the start of the war. Other rumours seem to have spread on their own, but no-one seemed to even consider Rhaegar and Lyanna as possibilities. The victorious rebels wrote their own narrative of the war, in which Rhaegar abducted and abused Lyanna for months before she died of an illness (the story spread by Eddard and the only other confirmed witness to the events, Howland Reed) just as Eddard reached her side, having struck down the honourable knight of the Kingsguard, Ser Arthur Dayne. Eddard returned Dayne's sword Dawn to his sister Ashara, only to find that she had given birth to a son, a result of their earlier crossing of paths, and he took the son home to Winterfell to raise as his own, before the heartbroken Ashara threw herself to her death. The singers must have been stampeding to be the first to spread such a romantic story around.
In the second novel, A Clash of Kings, Daenerys Targaryen has a vision whilst in the House of the Undying in Qarth. She sees Rhaegar and Elia Martell, doting on their newborn son Aegon. Rhaegar says that "his is the song of ice and fire" and that "he is the prince who was promised". But he also says that "the dragon has three heads" and "there must be a third". A Dance with Dragons expands on the relevance of this: bearing Rhaenys and Aegon almost killed Elia, whose health had always been delicate, and Elia was told by the maesters that she could bear no more children. If Rhaegar indeed wanted a third child, the child would have to come from another woman.
When he was young, Rhaegar was inclined to reading, performing music and writing poetry. He had little appetite for war or conquest. But something that he read made him take up the sword and lance. He proved reasonably effective, if not outstanding, but clearly believed that his destiny would require him to fight. He wrote long letters on the subject to his grand-uncle, Aemon, serving as maester at Castle Black on the Wall. Rhaegar had become obsessed with the prophecy of the last hero, a great warrior who would save the world in the second War for the Dawn (the first, eight thousand years earlier by tradition, had seen the Others defeated, the Long Night ended and the Wall raised). Rhaegar initially believed that he was the prince, who would be born amidst "smoke and salt" under a bleeding star, because he had been born on the night of the terrible fire at Summerhall that killed his great-grandfather, King Aegon V. But later he believed it referred to his children. He also believed, either from this prophecy or another, that he would need to have three of them, like a modern version of Aegon the Conqueror and his sisters Visenya and Rhaenys. He even planned to give them the same names.
Last week's episode of Game of Thrones seemingly confirmed that Jon Snow is the son of Rhaegar and Lyanna. Producers David Benioff and Dan Weiss had been challenged by George R.R. Martin to guess the identity of Jon Snow's mother and he only agreed to let them try tackling the TV series after they guessed correctly. So we can take this as confirmation of the theory (especially after HBO published a slightly over-the-top infographic expanding on it).
The question then becomes, is it even relevant? Isn't Jon still a bastard? Well, probably not. Aegon and his two sister-wives were legitimate Targaryen children, and Rhaegar likely would have wanted for his "three heads" to be legitimate as well. The Targaryen practice of polygamy had apparently died along with Maegor the Cruel, but it was never formally repudiated. It seems that Jaehaerys I let it drop as an (informal) concession in his negotiations to end the war with the Faith Militant. Even the Faith and Citadel acknowledged the children from both lines of those two polygamous marriages (Aegon's and Maegor's) as being legitimate. So there was nothing stopping Rhaegar from marrying Lyanna. Indeed, Elia seemed pretty sold on the prophecy herself and Dornish views on such relationships are far more relaxed than elsewhere in Westeros.
"Promise me, Ned..."
That may be somewhat thin ice to base the theory on. But much more convincing is the fact that when Eddard found the Tower of Joy and his dying sister, he also found three knights of the Kingsguard waiting for him: Ser Gerold Hightower, the Lord Commander of the Kingsguard; Ser Arthur Dayne, the Sword of the Morning, reportedly the greatest warrior in the history of Westeros; and Ser Oswell Whent, whose honour and trustworthyness was beyond repute. For three of the seven Kingsguard to be deployed to protect the prince's mistress, even her and a bastard child, seems like ridiculous overkill, not when a full-scale war is underway and not when the fate of the kingdom, House Targaryen and Aerys and Rhaegar hang in the balance based on events elsewhere. If it had been Arthur Dayne who had found and battled Robert Baratheon at the Trident, it is rather improbable that Baratheon would have survived the encounter (as it stood he was wounded by Rhaegar, a vastly inferior fighter to Dayne) and the rebellion would have ended then and there. If any of the Kingsguard had been with the Mad King, it is unlikely that Jaime would have been able to strike him down. Protecting the prince's wife and child (and heir, in the event of King's Landing falling) is really the only plausible reason why those three would be at the Tower.
So the question now is how will the truth be revealed? Bran can tell Jon and Sansa and they'll probably believe him, but who else will? There may be a septon somewhere who married Rhaegar and Elia (assuming they didn't just seal their vows between them in front of a heart tree, which may be how Bran sees it in the books but doesn't help the proving case very much), and both Wylla and Howland Reed know the truth. But it seems a tad unlikely that they'll all be believed. The dragons accepting Jon as a rider may be a clue in the books, but during the Dance the dragons also accepted non-Targaryen riders as well (albeit all suspected of having a drop of Valyrian blood somewhere). The TV series, which depicts the Targaryens are being fire-proof at all times, may be able to prove it more easily but Jon's Stark blood may interfere with that (and we know he was burned battling the wights whilst defending Jeor Mormont, so that theory might already be toast).
Proving a theory that was already 99% certain anyway is one thing, but how much impact this revelation will have on the storyline, both in the books and on screen, remains to be seen, and a source for additional speculation for at least a couple more years.