This is by far both the longest and hardest part of the game, even for experienced players. Mount Itoi has several "tiers" of enemies, progressing from tough to murderous. You don't want to fight all of them, or you will simply run out of supplies and PP, and you will be left unable to heal yourself and you will die. If everybody's around level 30, which they probably are, you're probably well enough off. (Don't worry too much if Teddy's a bit underleveled. He'll handle himself just fine.)
First you will bumble about in the caverns. In the first screen you can acquire the Katana, Teddy's best weapon. You can also find Hank's Bat elsewhere in the caverns. Likewise, you can find the Iron Skillet, but it is very marginally better than the boomerang (only 4 points stronger) and Anna is never going to be strong enough to physically attack anything by this point in the game. Make sure a Franklin Badge is in her inventory, so that she won't get hit with PK Beam γ (if others get hit, she can revive them). If you have a second badge, give it to whoever else you would rather be alive (probably Ninten or Teddy). If Anna falls in battle, you can use the Onyx Hook to go back to Magicant, heal up, and try again.
Once you get out of the caverns, the journey is only beginning. You will come across enemies such as Mega Borgs, which are not particularly strong, and Grizzly Bears, which are deadly. A grizzly can deliver 100 HP damage to a party member with full armor (you equipped everybody will full armor a long time ago, right?), and you don't want to burn PP needed to fight and heal the wounds. Run from them.
Eventually you'll find a house. Go into it, talk to the healer (he'll restore everybody to prime condition for free), save the game on the phone and only then proceed into the next room of the house. Ninten and Anna will be granted some privacy, which they'll use to start dancing. Then suddenly...
Remember R7037? Remember how you were screwed if you weren't in the tank? Well, you're not in a tank, and you're now facing R7037's cousin, R7038. Yep, you're screwed. There's nothing you can do, so do whatever you want. After your third party member falls, the tank will roll up and destroy the bot... it's piloted by Lloyd! (Note: you'll have your money halved because of losing the battle. That's OK, though, because money absolutely does not matter by this point.)
You then return to the house between Ellay and the caves. Sadly, Teddy is in critical condition. Lloyd takes his place -- and his inventory items. You can either start the long trek back up the mountain anew, or if you can't be bothered, you can intentionally die so that you go back to the house on the mountain (if you saved there).
North of the house, you'll come across a lake. Hang to its eastern side and follow it. You'll find a boat. Hop in (Lloyd will fix it), locate the whirlpool, and go into it. After a few screens, you'll meet the robot EVE. You'll then exit and be brought back to outside the lake. Do not attempt to walk back south or you will encounter R7038XX. This is an encounter you will be unable to avoid, but it's better to put it off because EVE will handle your battles quite well for you. You'll eventually come across a cave opening. Inside is the Sea Pendant, which defends against all PSI attacks. Give it to Anna, have her equip it, then just toss whatever pendant she was wearing (unless you want to give it to somebody else). Soon you'll meet R7038XX, and EVE will sacrifice herself to save you. CHECK the wreckage and you will find the seventh melody. (This is the second time Lloyd saved your skin: without Lloyd, you couldn't get EVE, and you would have been killed by R7038XX.)
You'll eventually come to a tombstone. (Giegue's lair lies just beyond, but it's blocked by a stone.) CHECK the tombstone and you will learn the final melody. You should have all eight melodies. In the original Famicom version of the game, you will warp to Magicant; in others, use the Onyx Hook to go there yourself. Go to Queen Mary and speak to her. After you sing the song, Magicant will fade away and you'll return to the tombstone on Mount Itoi. Walk north, and you'll see that the stone that was blocking the way will be cleared. You're ready to take on Giegue.
The final battle
Enter the cave. In the English prototype version, you will see a cave off to the right where you will see some prisoners of Giygas. (In the Japanese version, you'll come across them earlier on.) It's just for show.
Walk north -- make sure everybody has full HP, now -- and you'll come across the big guy himself: Giygas. (He's named Giegue in the English prototype, but see naming confusion above.) Giegue is easy if you know how to handle him, but extremely tough if you don't, so pay attention. He'll start with a monologue, with an incomprehensible attack with each sentence. Have Ninten cast PSI Shield β immediately (but don't bother with Defense Up β because it won't help). That's the key to this battle, because you'll suffer extremely heavy damage without it. After that, Ninten can successfully complete this battle alone if he has enough PP and keeps using Lifeup γ as appropriate, but it's better to keep other party members alive to get it done faster and more safely, especially if Ninten is low on PP. QuickUp on your characters might be helpful as well. Don't do anything else during Giegue's monologue other than healing, and reviving as necessary, guarding otherwise. Once Giegue stops talking, you can start singing. (In the English version, you can sing before then, but it will be ineffective.) Each time, the song will be more complete before you're interrupted. You will win the battle after singing the complete song.