Captain Toad

From SMO.wiki

Captain Toad is an NPC who appears in all kingdoms except for Darker Side, Ruined Kingdom, and Cloud Kingdom. The first time he is talked to in each kingdom, he gives Mario a Power Moon. Captain Toad will only appear in a kingdom once peace has been achieved in it. Whilst talking to Captain Toad the song named "Toad Brigade Member" will play.

Kingdom Location
Mushroom On top of the Crazy Cap store
Cap On top of Top-Hat Tower on the arena where Topper was originally fought
Cascade On a ledge under the Madame Broode boss fight arena to the right of the Moon Rock
Sand In the Desert Oasis section of Sand Kingdom (hidden as a fish, must use Lakitu to unlock Captain Toad)
Lake At the bottom of the well in front of the Water Plaza Entrance
Wooded On a distant platform east of the mainland
Lost In a cave below the Swamp Hill checkpoint
Metro In the very back of the kingdom on a thin, red ledge.
Snow In a small cave covered by snow
Seaside On a platform above the Above Rolling Canyon checkpoint
Luncheon On a small island of salt near the Start of the Peak Climb checkpoint
Bowsers To the right of the Outer Wall checkpoint
Moon Near the Odyssey, looking at the Earth with several other characters
Dark Side In the tunnel between the Rango and Mecha-Broodal fights

Here is a video which demonstrates how to get to each location:

https://www.youtube.com/watch?v=h1TgVcKiFxM