How do Southern people discern Night's Watch deserters from truthful brothers sent south?

Question

Night's Watch deserters are sentenced to death, as we've seen in the very first episode of Game of Thrones. A man dressed all in black is apprehended by Stark men and brought before Lord Eddard Stark. Lord Stark sees him as a deserter and sentences him to die (and then executes that death penalty).

However, there are men of the Night's Watch south of the Wall, on a legitimate mission or on some kind of allowed leave. For instance, we have Benjen Stark visiting Winterfell when the king and his party is there. There is also Yoren, who travels around Westeros in search of new recruits.

I could imagine that the Warden of the North (and other lords in the northern part of Westeros) would have a good idea of who would be allowed further south and whose appearance would raise suspicion. But I reckon the southern lords don't have as many visits from the Night's Watch, so they might not know who would be allowed to be there and who wouldn't.

How would lords who are rather unfamiliar with the specific brothers of the Night's Watch discern deserters from brothers sent out for some reason?

That ends my question, but there is a spoiler from the season 5 finale that continues the question a bit more:

Sam is sent to Oldtown to become a Maester, so he can replace Maester Aemon at Castle Black. But he is riding together with Gilly (a woman!) and her baby (a baby!), which might raise a lot of suspicion from people who don't know what he is sent out to do. What prevents southern lords of sentencing Sam as a deserter from the Night's Watch?

Answer 1

As mentioned in comments, a Night's Watch brother on official business could have a document authorising him to leave the Wall, bearing the Lord Commander's seal.

To be clear, a sealed medieval document does not have to be sealed shut. It was common to affix a seal to the bottom of a document on a ribbon, as in this example:

Or even several different seals:

The people the brother met (including nobles) might be illiterate. However, they would be able to recognise the picture on seal of the Lord Commander -- which would be particularly well known in the North.

As for what happens in the South: Night's Watch deserters are much more likely to be found in the North. It's a very long way from the Wall to King's Landing -- and any deserters who get that far would probably manage to steal some clothes along the way, so they are no longer wearing Night's Watch black.

So, authorities in the South don't have much reason to be suspicious of travellers dressed entirely in black -- any such people they encounter are likely to be Night's Watch brothers on official business, not deserters.

Answer 2

It's easy. Once they have gotten to the South, the ones wearing Night's Watch black are legitimate members of the night's watch.

Deserters have long since stolen some clothes at a village.

Only those very close to the wall will ever encounter a nightswatchman deserting who has not had a chance to change.

The real difficulty is telling which people dressed as peasants are actually nightswatch deserters.

Answer 3

It has already been answered that it is possible that Members on business of the Watch would carry identification and authorization documents with them.

Few things have not been discussed yet:

Size 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.

Necessity to steal provisions

A person wearing black clothes south of the neck was always viewed with suspicion and people kept an eye on their movements. That was because NW men seldom had business down there except the few wandering recruiters like Yoren. From Jon's POV in AGOT:

A stranger wearing black was viewed with cold suspicion in every village and holdfast north of the Neck, and men would soon be watching for him.

That makes it paramount for the deserter to steal clothes which may lead to hue and cry by the owner of the stolen clothes, leading to capture of the deserter. This was not limited to clothing only. If by mischance, the deserter had any bit of black equipment on him, he would be done for. From same chapter in AGOT:

His longsword and dagger were sheathed in black moleskin, and the hauberk and coif in his saddlebag were black ringmail. Any bit of it could mean his death if he were taken.

Also, The deserter would have to find food as well. That would involve stealing from villages or hunting in the woods. Hunting had the risk of running into some Lord's hunting party and stealing had the risk of the owner raising an alarm over missing food, animals or goods.

Warrants issued from Castle Black

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:

Once Maester Aemon’s ravens took flight, Jon knew he would find no safe haven.

The necessity to remain out of sight

Even if someone made it all the way to South without encountering any problems, he would have to live a lie and change his entire life's story. But as soon as he caught attention of someone, it was unlikely that the story would hold. From Jon's POV in AGOT:

He was who he was; Jon Snow, bastard and oathbreaker, motherless, friendless, and damned. For the rest of his life-however long that might be-he would be condemned to be an outsider, the silent man standing in the shadows who dares not speak his true name. Wherever he might go throughout the Seven Kingdoms, he would need to live a lie, lest every man’s hand be raised against him.

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.

Answer 4

I would assume that Ravens would be sent to every part of the world telling the lords the identity of the deserter.