Train Troubles
All you need to do is to break the rock in front of the train in toad town. To do this just choose Bombette as your partner and press to get her to blow up near the rock. Then you may catch the train to Mt. Rugged.
Letter Patrol
Once off the train, check the bushes outside. one has an egg (+ 5 HP anytime in battle) every time you exit and re-enter the area.
Desert of Dreams
The Mysterious Moustafa
When Mario enters the outpost, he wanders around until you see a mouse thief running from a shop. When you try and enter the shop, it says it's closed. You continue to the next area and see a mouse running from another mouse. You head back to the shop to find it is open again. Buy a Dried Shroom and Dusty Hammer in that order. The shopkeeper will say you must get in touch with Moustafa and to go see him. Again go to where you first saw the mouse to find the door will open this time. Follow the path to a door on top of the roof and enter the door. The mouse will reveal himself as Moustafa and then tell you how to reach the ruins!
Ruin Run
To get to the ruins go north as much as possible as soon as you get out of the town then go west till you get to the area with the one rock in the middle. Use your new item on it and the ruins will come out the sand. Go inside and beat the Pokeys.