This first thing to realize here is that there is no correct answer. It will depend of a lot of factors.
They obviously can't stay silent about this of course, but neither can they attack another samurai. After all, the Imperial might just be doing his duty, even if said duty isn't honorable. And ambushing a samurai is definitely not the honorable thing to do. So they can't just attack the guy on the spot. However, they can confront him.
There are 2 solutions I can see :
They confront the guy. If he attacks them, they can defend themselves. But if they kill him they might get into a lot of trouble. However, if the Imperial says this is not of their business and he acting for the good of the empire, there is nothing they can do about it. However the guy is now warned.
They could also report this to their superiors or to a magistrate of the lands they're in. If they're clearly outranked, the magistrate won't be able to act on their testimony though, even if they bring proof. Material evidence is nothing compared to the word of a high ranking samurai.
Asking the help of an emerald magistrate would be the better course of action. He will have the authority to organize a search and to condemn the Imperial if something is found. He will also have the necessary contacts to know if the Imperial actions are authorized or not.
However, if nothing is found, the PCs will be in a bad situation... the Imperial might pull a few favors to make life for the PCs very difficult (called back to their land, papers to travel or cross territories refused, etc).
To find your own answer, you should :
If he's alone and doing this for profit, the emerald magistrate will be able to guide the PCs to a law abiding solution, finding proof and having the authority to deal with the imperial.
However, if the Imperial was doing this for duty... The NPCs will probably have a lot of problems.