Welcome to the Underworld, a place so large you seem very small in comparison. In fact, you are only a couple of pixels across and can barely discern yourself on the screen. The dinosaurs here a quite powerful, and unless you feel the need to gain a few levels it isn't worth it to fight them. If you would like the Magic Fry Pan, you have a 1/128 chance of getting it by fighting the purple dinosaurs known as Chomposaur. Pretty soon you'll be able to buy her ultimate weapon, the Holy Fry Pan, so it is not really worth the time to find the Magic Fry Pan.
Upon entering, the first thing you should do is head west and north so that you may save within the fenced in area. If you head to the west of the save point and stay along the northern wall, you'll come across a Brain Food Lunch. Head back in the direction you came and continue east. Hug the southern wall and you'll stumble upon a Horn of Life in the corner. Moving straight north from here will yield a Sea Pendant, which protects you from freeze, fire, and flash! Moving along the wall to the west and then back north will yield a Guts Capsule. Head back to the south-west and you'll find a small Tenda Village with another save point and a talking rock.
Walk up to the gate and the Tendas will take your Tendakraut and let you in. Speak to the rock in the corner and he'll direct you to Fire Spring. Before you go, make a quick trip to the store and pick up all the new offensive and defensive items. Don't miss out on Paula's best weapon here. If you need more money, there is a Tenda who acts as an ATM, though he charges an insane processing fee. If you don't want to pay it, you can always teleport somewhere else and teleport back.
Head to the west and south toward Fire Spring. On the way you will notice a cave to the north. There is nothing of interest here at this time, though it will be important later. Continue to the south and when you are forced to move east, head back north a bit to find Poo's Cloak of Kings. At this point you should equip Ness with the Sea Pendant, Paula with the Flame Pendant, and Jeff with the Night Pendant. Head south and heal up at the geyser, then save at the bird to the west. When you are ready, enter the cave.