He should've given you a key item called Rail Clue Sheet. Using it will give hints on where to dig in the desert to find the three pieces of the map. All three are in ruins in the desert, so look for screens with broken walls and tiles, then use a shovel in places that fit the clue sheet's descriptions. Once you have all three map pieces you can return to Rail outside the inn at night.