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 (Gared) 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?

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?