We are left to make our own inferences, and it may seem puzzling to the modern reader. Nowadays we are used to fast travel, cell phones, and electronic communication. How did people manage without them? But if Shaw's audiences considered this question, I don't think they'd have had much trouble with it. They'd have assumed that Bluntschli left instructions with his military contacts about where to find him.
In the stage directions, Shaw has emphasized the relative backwardness of his setting. There are no mentions of telephones, or even of a train; under conditions like these, a professional officer like Bluntschli would be accustomed to having a rider deliver important messages to him. It would have been essential for efficient communication, and if Bluntschli is still in the army (which seems to be the case), he may even have been required to tell his superiors where he could be reached.
Petkoff's village is small and Petkoff a prominent citizen, so Bluntschli wouldn't have had to leave a detailed address of his whereabouts. He might simply have left word that he'd be in that particular village, and the messenger would have been able to locate him there by asking around. For instance, the messenger might have asked at the local inn, if one existed, and been directed to Petkoff's house.
Do we have reason to think the village is far enough away to make all this necessary? The contemporary British audience probably didn't have an idea how far the village (near Dragoman Pass) was from Bluntschli's last known location (in "Peerot," or what is now called Piro, Serbia). But I don't think they would have been surprised if it represented a distance that implied many hours of travel. And actually it did. Google maps calculates the distance between the two places as about 46 km or 28 miles -- a sizable journey back then if it meant rugged terrain and limited or no train access. This, then, is consistent with the possibility that Bluntschli had anticipated spending the night in or near the village.
In short, I don't think Shaw saw the arrival of the messenger at Petkoff's house as a mystery or a loose end in his plot. He was operating with the background assumptions of how communication typically worked for a man of Bluntschli's status and situation.