Return to Answer

Conclusion

1. Northerns mostly live in small communities and thus are bound to know all the residents of their community. They would instantly know an outsider. North is very huge which means that a deserter will have to go through a lot of communities and answer a lot of Questions which can lead to suspicion by people.
2. To survive, a deserter will have to steal or rob. That would put undesired attention on him and might result in arrest by some local Lord.
3. Castle Black issues warrants to all concerned lords in case someone deserts. So most likely he would be taken by patrols on his way south.
4. South of the neck, every man in black was viewed with suspicion because Night's watch usually had no business there except for recruiting or gaining grants which was done by wandering crows. So if there is a man in black without any document authorizing him to ask for prisoners as new recruits or for begging aid, It is probable that he is a deserter.

As soon as Castle Black became aware of the desertion, warrants will be issued for the arrest of the deserters which may include description of the man's physical appearance and other distinctive traits. The warrants will be received by all the concerned lords who will then forward them to their patrols and subjects. Those warrants were sent by ravens so the word spread faster than the deserter could move. From Jon's POV in AGOT:

As soon as Castle Black became aware of the desertion, warrants would be issued for the arrest of the deserters which may include description of the man's physical appearance and other distinctive traits. The warrants would be received by all the concerned lords who would then forward them to their patrols and subjects. Those warrants were sent by ravens so the word spread faster than the deserter could move. From Jon's POV in AGOT:

North was almost as big as rest of the seven Kingdoms combined. Population is very sparse and people live in closely knitted communities, mostly in villages because there is only one true city in North which is White Harbor. In villages, people tend to know who is who. So if a stranger walked in on some settlement, Questions will be asked. Questions will lead to suspicion and thus eventual capture of the deserter before the deserter ever made it out of the North.

North was almost as big as rest of the seven Kingdoms combined.

From Eddard's POV in AGOT:

“I was starting to think we would never reach Winterfell,” Robert complained as they descended. “In the south, the way they talk about my Seven Kingdoms, a man forgets that your part is as big as the other six combined.”

Population is very sparse in the north. From Eddard's POV in AGOT:

Robert snorted. “Bogs and forests and fields, and scarcely a decent inn north of the Neck. I’ve never seen such a vast emptiness. Where are all your people?”

Presumably, people live in closely knitted communities, mostly in villages because there is only one true city in North which is White Harbor. 

In villages, people tend to know who is who. So if a stranger walked in on some settlement, People will know him for an outsider and Questions will be asked. Questions will lead to suspicion and thus eventual capture of the deserter before the deserter ever made it out of the North.