To make the mayor unlock the path to Giant Step, you defeat the Sharks gang.
Talk to the Mayor
After you defeat Frank, talk to the Mayor in the Onett Town Hall to get the key to the traveling entertainers' shack. To reach the shack, go west from the town Library. Use the key on the door to unlock it. After you unlock the shack, but before you go inside, talk to the guys wandering around outside the shack and one of them will give you the Travel Charm, which increases your defense.
Prepare for the Cave
Be sure to have some food in your bag before you go into the cave. You will need it if you run out of PP to heal yourself.
Go Through the Cave
Go through the shack, then enter the cave. You will encounter Attack Slugs, Rowdy Mice, and Black Antoids in the cave. When fighting these enemies, heal up if your HP is 15 or lower. When fighting Black Antoids, attack the Black Antoids first if there are other types of enemies, because Black Antoids can call for help. Keep in mind that Black Antoids can use Lifeup α.
From the entrance of the cave, go left. There is a room along the way that contains a Skip Sandwich. This heals you up about as much as a Cookie, but it makes you walk around twice as quickly.
Exit the Skip Sandwich room and go west. Go up the rope (the door to the left of the rope just leads to an empty room).
After you climb up the rope, go east. You will find another rope. Before you climb it, go through the door to the right if you want a Cold Remedy. Then leave the Cold Remedy room and climb up the nearby rope.
After you climb the second rope, go northwest to find a door to the outside. You will usually find a Magic Butterfly outside. (If not, go inside and come back out again.) Magic Butterflies restore some of your PP. The butterfly is likely to reappear if you go inside and outside again. Use this to heal up all of your HP and PP before you continue.
In the next cave area, go southeast to find a gift box containing a Hamburger. Then go north and go through the door there.
After you go through a small cave, you reach a room with a series of ropes going up. Climb the ropes to find a large sparkle that is guarding a door. This is the boss of Giant Step. Talk to it to start the battle.
Titanic Ant can use PSI Magnet, so you will probably run out of PP before the end of the battle. Keep in mind that the Skip Sandwich does not restore very many HP, so you should not use it during battle.
There are two Black Antoids next to the Titanic Ant. They can use PSI Lifeup to heal the Titanic Ant. They will run out of PP after about five turns.
Titanic Ant can cast Shield α, which will reduce the effectiveness of your physical attacks.
Use PSI Rockin α on the first turn if you have it. This will kill the Black Antoids immediately. After that, you might want to only use PP for healing. Heal up if your HP is around 40 or lower.
Get the Melody
After Titanic Ant is gone, go through the door that it was guarding. Approach the footprint to record the melody of Giant Step.
At this point, whenever you sleep, Paula might contact you in your dreams.
Go to the Police Station
Now that you defeated Titanic Ant, all of the monsters in the cave will run away from you.
When you exit the cave, a police officer tells you to come see him at the police station.
If you are below level 7, try to level up before continuing on. You should also bring some Hamburgers with you.
The police station is east of the arcade. In the police station, talk to Captain Strong. Say Yes when he asks if you really want to go to Twoson. He will lead you into a back room where several police officers will attack you.
You will have to defeat four cops (the fifth one runs away). You can't heal up between battles, so be sure to heal yourself during the battles. The cops' strongest attack is the Crushing Chop. Keep your HP above 35. Try to conserve your PP for the final battle.
After defeating the four cops, Captain Strong attacks. Keep your HP above 50. Use PSI Rockin α a couple of times to defeat him (but there is a chance that the attack will not work sometimes). If you need to conserve PP for healing, use regular attacks until he is defeated.
Afterward, Captain Strong will radio the officers who set up the blockade to the south, telling them to let you through. Now you can go south to Twoson.