(This answer is based on the US banking system; if that isn't where you are, please edit appropriately.)
There are probably two places the thief could go to cash the check:
The issuer's bank
Third-party banks are unlikely to want to cash a check drawn on a different bank for a payee who isn't their customer. So notifying both of these banks would be a good start.
Also, hopefully the thief does not look like you and won't be able to pass using your ID. The thief will also have to forge your endorsement on the check - if he goes to your bank, they can check it against your signature which they have on file, and hopefully it won't match. (The issuer's bank wouldn't notice that, of course, so read on.)
Even if the check is cashed, you should ultimately be okay, as I understand it. The issuer of the check still owes you the money; he can't prove he's paid you until he has the cancelled check (or its image) showing your valid endorsement. So he needs to give you another check, eventually. (This assumes the check was payment for a debt of some kind; if it was a gift or some other sort of voluntary payment, he could at this point change his mind and decide not to pay you after all.)
The issuer should be okay too. If the check is cashed and debited from his account, he should go to his bank and tell them the endorsement is forged. They may ask you to sign something where you state under penalty of perjury that the signature isn't yours. Then they will re-credit his account, so that he can pay you again.
(Normally the bank that cashed the check will be on the hook for the loss; it was their responsibility to make sure they were paying the rightful payee, and they failed in that responsibility. Various procedural issues can shift that liability between banks, but ultimately it shouldn't be either customer who suffers unless someone did something really negligent, like not reporting the theft for months.)
Obviously this would all be much simpler if the issuer can call his bank right away and stop payment. This can be done over the phone or online, so "out of town" shouldn't be an issue unless he is out in the woods or something. If he can talk to you, he can talk to them.