Exit the prison by hopping over the hole to the left of your cell. This will take you to a building with a PC in it, and once outside there is a patch of grass and Palette Blue.
Speak with Palette Blue, who will give you your first Cage Key.
Head back inside, unlock your cell, and explore the prison. The player should be able to reach the bath room, the weight room which has a nurse for healing pokemon, and other cells at this point.
Find the Fluffy Coat and two Cage Keys on 1F by going through the doorway near the stairs. There is another Cage Key hidden in the top bath. Go to the weight room and talk to the prisoner at the table, he will give the player one more Cage Key.
You should now have 4 Cage Keys, now you should challenge Cooltrainer Conner by unlocking his cell. He will tell the player some information about a password for the basement door.
Open Palette Black's cell. After talking to Palette Black, they will give you the Roof Card.
Make your way to the roof by going up a flight of stairs and avoiding being seen by the guards.
Once you find your way to the roof stairs, be prepared for a battle. Upon reaching the roof, there will be two guards waiting who will challenge you to a battle. Once you defeat them, they will tell you to talk to the officer in the weight room who will tell you the password to the basement door.
Head down to the basement and unlock the door. Once inside, the player has the option of opening the cage holding the Legendary Pokemon Fambaco.
You will find your rival down here trying to dig his way out of the prison. Challenge him to a battle, and upon defeat he will give you HM05 Strength.
Now that you have Strength, you can move the boulders outside the building and make your way around the island. You're essentially free!