Yeah, he appears on land somewhere in all of the areas besides the aquarium. You also always find a new piece of clothing where he lands, which is nice. The last three are harder because he only appears when certain environmental conditions are met. He always tells you the next area he will visit and what, if any, conditions need to be met for him to appear. I think he was actually put into the game specifically to force you to explore the land, honestly. There are a number of things like that, where they force you to do some totally unrelated task in order to complete the task you really want. For instance making you clear the maps to get legendary creatures, making you train your dolphins before it will let you clear all the maps, and so on.