From Bean Valley, you defeat Megasmilax and find a beanstalk seed, and the vines in the clouds lead you to Nimbus Land.
Explore Nimbus Land
If you talk to the two guards, they tell you that you can't visit the hot springs if you aren't royalty. So just jump on the spring, and you'll find an area with two springs. The spring on the right takes you to the world map, where you can come and go from Nimbus Land as needed. There is a hole to the southwest that takes you back to Bean Valley. The spring on the left takes you to the main part of Nimbus Land. Jump on that northwest spring and there will be a cutscene.
If you want to go back to the world map, you can fall back down the hole in the clouds southwest of the castle. After the cutscene, you can talk to everybody and visit the shops. There is a hidden chest above the boxes in the item shop that contains a Frog Coin. It's one square southwest of the box that doesn't have other boxes on top of it, but you have to jump from the highest level to reach it.
Go into the house northwest of the castle and check on the statue that looks like Mallow. There will be a cutscene. When Garro asks you to come over here, make sure that you are healed up and have the items that you need. Then stand in front of him. He will ask if you are ready. If so, say Yes. In a cutscene, Garro will take you into