|Theories may be removed if ...|
Jon Snow has the following thoughts on his mother in A Game of Thrones:
. . .Even his own mother had not had a place for him. The thought of her made him sad. He wondered who she had been, what she had looked like, why his father had left her. Because she was a whore or an adulteress, fool. Something dark and dishonorable, or else why was Lord Eddard too ashamed to speak of her? 
Another theory claims Jon's mother was Ashara Dayne, his father being likely Eddard Stark, who was in love with her, or his older brother Brandon Stark. Lady Dayne was said to be with both of them during the Tourney at Harrenhal. According to Ser Barristan Selmy, one of the Starks bedded her at the tournament and got her with child. It was also known by many that she was pregnant before she killed herself by jumping from the tower of Starfall, also called the Palestone Sword, a tower on Starfall's cliff by the sea.
Though Ser Barristan believes the bastard child of Lady Dayne was a stillborn girl, some still believe Ashara Dayne to be the mother of Jon Snow. Among those who believe so is Queen Cersei Lannister. Both she and Lady Catelyn Stark have heard this rumor, but Eddard refuses to answer Catelyn when she asks if Ashara Dayne was Jon's mother.
Wylla, the wet nurse at Starfall, is another possible mother. According to King Robert Baratheon, he recalls Ned bedding a wench during the Rebellion. On their way down the Kingsroad from Winterfell, he tries to recall her name, calling her, "Your bastard's mother." Ned says her name was Wylla, but refuses to talk more about it.
Catelyn recalls how with the war at an end riding to Winterfell... meeting Jon and his wet nurse. It very likely that this wet nurse is none other than Wylla because Ned went to Starfall returning the sword Dawn to Lady Ashara Dayne. These events are the source for two rumors that circle about Winterfell: the death of Arthur Dayne by Ned's hand and that Ashara Dayne is Jon's mother. It is Ned that silences this rumor about her. There are only two possible sources for these rumors; Wylla and Lord Howland Reed; however Howland is lord of Greywater Watch thus making Wylla the most likely candidate. 
Lord Edric Dayne tells Arya Stark that Wylla is Jon's mother. He recounts to Arya Stark that he was a milk-brother to Jon Snow since Edric was also nursed as a baby by Wylla. He also claims they are not blood brothers either. However Arya notes that all Dornishmen are liars. In the case of Edric, it may actually be a lie perpetuated by Wylla to protect the true parentage of Jon Snow. 
The Fisherman's Daughter
Lord Godric Borrell recounts to Davos Seaworth about a fisherman and his daughter who brought Eddard Stark in secret across the Bite to the North at the beginning of Robert's Rebellion. The fisherman died in a storm that almost short-ended their journey, but his daughter continued and successfully saw Ned to the Sisters before the boat went down. If Lord Borrell is to be believed, Ned left her with a bag of silver and a bastard in her belly, which she named Jon Snow after Lord Jon Arryn.
Many readers believe that Jon is not the son of Eddard Stark. Instead, he is the son of Prince Rhaegar Targaryen and Eddard's sister Lyanna Stark. Rhaegar and Lyanna disappeared together to the Tower of Joy early in Robert's Rebellion. There, it's believed, Rhaegar leaves a pregnant Lyanna to defend his family's dynasty.
At the end of Robert's Rebellion, about one year later, Eddard and his companions find three of the Kingsguard at the Tower of Joy: Lord Commander Ser Gerold Hightower, Ser Oswell Whent, and Ser Arthur Dayne. The reasons for their presence and the ensuing fight are unknown, but defending the unborn son of the Heir Apparent would be a good reason to have been posted. The only known survivors of the fight were Eddard himself and Howland Reed. Eddard recalls his sister dying "in a bed of blood," where he made her an unknown promise just before she died.
Also, while Robb, Sansa, Bran and Rickon are said to have Tully features (hair color, eyes), Jon and Arya are said to be closer in appearance (which had made Sansa believe Arya was also a bastard like Jon, until her mother put Sansa's theory down). Arya is said to resemble Lyanna. In the same line of comparison with his "siblings"; while all their direwolves are described having dark fur, Jon's, Ghost is white - a color oft associated with Targaryen features.
Further evidence to the truth of this theory in the eighth Eddard chapter of A Game of Thrones, in which Ned contemplates the significance of King Robert's bastards. As he muses, Ned's thoughts drift to Jon Snow, a logical segue, but also to his sister Lyanna Stark, the promise he made her, and to Rhaegar Targaryen, implying some tacit link between the three individuals.
Daenerys Targaryen's visions in the House of the Undying include an image of Rhaegar with his newborn son Aegon, proclaiming that "there must be a third" because "the dragon has three heads". Given that, according to Jon Connington, Rhaegar's wife Elia was believed infertile after two difficult pregnancies, and that Aegon the Conqueror himself had two wives, it is logical for Rhaegar to have attempted to fulfill the prophecy by having a third child with another woman. Another of the visions Daenerys sees is the image of a blue winter rose growing from a chink in a wall of ice, filling the air with sweetness. Lyanna was noted by Ned to be fond of winter roses, and he associates them with her death. Jon, who could be the product of Lyanna, is currently at the Wall.
If Rhaegar secretly married Lyanna, it would ironically mean that Jon is not a bastard despite his life having been defined by his believed bastard status to a great extent, and that he is the heir to the Iron Throne after Aegon VI Targaryen (although this last point is rendered moot so long as he belongs to the Night's Watch).
With Eddard beheaded by King Joffrey, Howland Reed is the only known living person who knows the nature of Lyanna's death and what she made her brother promise; however it is suggested that someone else may know:
...After that he remembered nothing. They had found him still holding her body, silent with grief. The little crannogman, Howland Reed had taken her hand from his.
The Game of Thrones episode "The Winds of Winter" shows that Jon is indeed the son of Lyanna Stark and that the promise she exacted from Ned was indeed to protect her son from Robert Baratheon, before she died in childbed in the Tower of joy. However, it remains to be seen if the books will follow the television series.
Quotes about Jon's mother
Jon: I don’t even know who my mother was. Tyrion: Some woman, no doubt. Most of them are. 
– Tyrion Lannister to Jon Snow