In the source material for the show, there were plenty of hints, but most of them were either cut out, or strongly downplayed, in the televised material. A casual viewer would almost certainly have had no idea that Jon was anything but Ned's child.
For starters, as far as we know, only two people alive (as of Season 1 Episode 1) know Jon's true parentage: Ned Stark and Howland Reed. They are the only survivors of the assault on the Tower of Joy -- Rhaegar Targaryen's castle where Ned finds Lyanna. Everyone else legitimately believes that Jon is Ned's son; that includes Catelyn, though she does not know who the moter is.
The most obvious (and it's not very obvious) clues for viewers that something is up have to do with the things we learn about Ned and Rhaegar from others who knew them. The accepted story of Jon's parentage is that Rhaegar Targaryen kidnapped Lyanna Stark, and Robert and Eddard's families started a war to get her back. During that war, Ned slept with someone else and had a child that he brought back to Winterfell with him.
Both of those actions are dramatically out of character for Rhaegar and Ned. We see Ned as an incredibly uptight, rigidly "proper" person, who's constantly doing "the right thing" even at great risk and expense to himself. For him to sleep around on his newly betrothed fiance while she waited at home seems highly unusual. Similarly, people who knew Rhaegar (particularly when they talk about him to Dany) paint him as honorable and noble, entirely unlike his whack-job father. It seems pretty unusual for him to kidnap a woman while married to someone else.
There are more subtle clues in the show as well, that you can piece together:
- The "real" story of what happens to Lyanna is kept secret by Ned
- Ned refuses to divulge the name of Jon Snow's "mother" to anyone, even Jon. (Though he does tell Jon that he will explain it all to him soon... then dies)
- A huge clue comes in Season 4's "Two Swords", where we learn the story of the Tournament at Harrenhall. Here, Rhaegar snubs his wife in favor of awarding a "favor" to Lyanna Stark instead. (This is shortly before she is "kidnapped")
In the novels, the "promise me, Ned." line from Lyanna is repeatedly shown to be in Ned's thoughts, especially as he's about to die. The book makes it very clear that what happened at the Tower of Joy was super important. And since the Tower of Joy is where Rhaegar was keeping Lyanna, and after leaving the Tower of Joy Ned "acquires" a baby boy, the hints are strong that Jon was born there.