From the Super Mario Wiki
The Desert Wanderer is a recurring Tostarenan tourist found in Super Mario Odyssey. He can be first seen near the entrance to Tostarena Town in the Sand Kingdom waiting for a taxi, which is revealed to be frozen in ice near the Inverted Pyramid. After beating Knucklotec, the taxi has thawed, and the Desert Wanderer will ask its driver, a New Donker, to take him to the Metro Kingdom.
After meeting him in the Sand Kingdom, the Desert Wanderer can be successively found in the Metro Kingdom, Cascade Kingdom, Luncheon Kingdom, Moon Kingdom and Mushroom Kingdom before finally deciding to return home. Once Mario meets him and the taxi driver in a kingdom, he will be presented with a Power Moon, and the wanderer will ask the driver to take him to a new location (except when he is in the Mushroom Kingdom, where he wishes to go back to the Sand Kingdom) based on what the driver can match to his description.