There are a number of times characters ask Jon Snow who he is, when he says his name many of them comment about him being a Bastard. How can people tell Jon Snow is a bastard just by his name?
Bastards are given a specific surname based on where they lived in Westeros. It varies depending on where you are born.
From The Tower of the Hand:
- The Crownlands: Waters
- The North: Snow
- The Iron Islands: Pyke
- The Riverlands: Rivers
- The Vale: Stone
- The Westerlands: Hill
- The Reach: Flowers
- The Stormlands: Storm
- Dorne: Sand
So since Jon lived in Winterfell (in the North), Jon Snow is the appropriate surname.
Ned Stark being a Lord of House Stark was a well known and prominent man in Westeros. It was well known he bore a bastard son. I think the fact that Jon Snow's bloodline preceded him is the reason people know.
With the fact that news travels via Raven or Rider the name alone wouldn't identify him. People may not know who he is by look but certainly join the dots when they ask him his name.
Taken from ASOIF Wiki - Ned returned home, bringing with him a bastard son, Jon, about whose origins he refused to speak, even to his own wife; he quickly silenced rumors that the boy's mother was the Dornish noblewoman Ashara Dayne - Referencing chapter 6 - Catelyn
This would create rumours amongst the lessers, the traders - thus the information spreads. Maybe not his looks but definitely the fact that he bore a bastard. Catelyn did not hide her disgust for Jon either. This is due to the fact he is a constant reminder of Ned's infidelity.
So in this series there are a few rules surrounding bastards.
If the Bastard has a highborn parent then so long as that highborn parent acknowledges the Bastard they can have a bastardy surname. EX: Gendry shouldn't have the last name Waters until Robert or the leader of his family acknowledges Gendry lives. So until Stannis agrees that Gendry is Roberts bastard he didn't have the right to call himself Gendry Waters.
The surname is based of the region the mother is from. This is mostly the same area the father is from but not always. In the books King Robert has plenty of bastards from different regions having the last names Rivers, Storm and Waters.
It is possible for two highborns to have a bastard, as such they will have the Bastard name of where the mother is from.
Bastards cannot inherit nor wear their family's sigil. Because of this when fighting for their families bastards will invert the family colors to make their sigil their own. EX: House Targaryen has the sigil of a red three headed dragon on a black flag. House Blackfyre was founded by a Targaryen bastard and their sigil is that of a black three headed dragon on a red flag.
A bastard can become legitimate should a king grant it. The lord parent can ask of this from the king and if the king believes this then it will be granted.