The Lost Underworld is big. Really, really big. So big, in fact, that Ness and his friends will be really tiny on screen. Nothing to worry about, though. They didn't shrink, or anything!
Go northwest from where you started. There is a geyser here that shoots out of the ground every once in a while. Before the geyser erupts, the ground will shake (and you can't move while the ground is shaking.)
The blue geysers here will heal you up. There is a red geyser that will heal all of your status ailments. To use it, just stand on the geyser when it isn't erupting, then wait for it to erupt. Once the water goes back down, you'll be all healed up. If you don't want to keep getting stuck by the shaking ground effect, just keep the geyser off screen. They don't erupt unless they're on screen.
There are good treasures around, so take your time. From the blue geyser, head west, then northwest. On the left side of a rocky outcropping, you'll find a Brain Food Lunch. Head east to reach a small pen with a bird phone inside.
Head east from there, then find a corner in the southeast where there is a Horn of Life. From there, go north until you find a Sea Pendant. Go south, and then west, and head north when you can to find a Guts Capsule. Head south from that, and start going southwest when you can.
You'll come upon a fenced in area. If you got the Tendakraut from the Tenda Chief, the Tendas in the pen will let you in. Otherwise, you'll have to teleport back to the Tenda Village, and then back to the Lost Underworld.
Once you're inside the Tenda area, talk to the talking rock. He'll tell you to go to Fire Spring. You can also buy some equipment upgrades here. There is also a Tenda who will give you money but will charge you the same amount that you withdraw. (If you are wondering about that Tenda's weird name, read Tomato's explanation of the name Ay-go Stikke.)
When you're ready, head west from the Tenda Village. You might see a cave entrance to the north as you go along. You can't do anything in there, but check it out if you feel like it. There is creepy music and a metallic tentacle. Yeah. More on that later.
From the cave entrance, head south. When you can, go northeast to get the Cloak of Kings. From there, head south, using the blue geyser if you wish, and saving the game with the bird phone if you wish.
Just northwest of the bird phone is Fire Spring.