In the north, there are clans of Dorn that collaborate with the Shadow and have the ability to wear clan colors and carry weapons (Chander, Esben, etc.). Those clans identify themselves by their colors and probably by documents coming from the traitor-princes. Non-clan travellers (tinkers, farmers selling at regional markets), travel at their own risk. Identured servants may have some form of marking that they work for/belong to a collaborator. That mark may be a brand or some identifiable mark on their clothing.
Most humans rarely travel far from their home village. Local shadow forces know who has to travel and who doesn't. It's valuable for the shadow to let farmers bring their production to the market so they ensure that the farmers make it safely. Over time, the local shadow garrison will know everyone who travels by sight and a fresh face will garner some interest.
In the south, there are a couple of differences. A large part of the population is in the major cities. Those nomads/free riders on the plains are targets for attacks. If you are mounted and not part of a shadow patrol, you are likely a target. Horses are reserved for the shadow friends/collaborators.
Gnomes are able to travel at will and humans that work on the Gnomish ships or at the gnome dominated piers are considered safe (for the most part) from the Shadow. Elves and Dwarves are normally attacked on site.
Legates normally have their own guards (orc or human mercenary) and an asterax. Having the right vestments, a proper holy symbol and all the other trappings necessary to pull off the bluff will be difficult. Probably the best way to impersonate a Legate is to ambush one and take his stuff, arriving at the nearby garrison about the same time as the Legate was expected. If you show up on the same day, in vestments that aren't stained in blood or cut up, you may be able to pull off the ruse.
Perhaps we could collect some excuses for travelling bands:
Disguise as Legate plus cohort.
Disguise as small band of farmers bringing their goods to a local market.
Disguise as convoys of Shadow troops (Sword brother or human collaborators, or even orcs if some PCs are orcs or dworgs)
Disguise as emissaries of traitor princes (using the right tartan)
Gnome "couriers" (if gnome)
Display of a legate's signet ring (which allows for travel - this can be an fake ring, cpoied on the legate's original) along with "secret orders"
Bribing the guards (orcs can be bought with fine gnomish liquor, humans with food or precious medicine...)
Membership of an underworld organization (such as the Hidden Hand) could provide the pCs with "special gestures" that allow them to show the guards that they belong to the Organization and that the guards' debts could be erased if they just let them go...
Blackmailing a legate could force him to deliver his signet ring, thus allowing its wearer free passage, at least in the legate's district...
PCs could be disguised as slavers, with the group's fey disguised as slaves (works best for halflings)
PCs could pretend to be a band of bounty hunters acting on behalf of the Shadow in the hunt of dangerous criminals (perhaps themselves?).