The Prison Town is set in the middle of a huge desert underneath the Gold Saucer. Escape is absolutely impossible.
Your mission is to find Barret, and then find a way out of the Prison.
You have to make your way into the desert and find Barret's old friend, Dyne. This is possibly one of the hardest sections of the whole game. The best way to find him is to talk to the three men on the bench, and do the exact opposite of what they tell you.
e.g. If they tell you to head North West, then head South East.
Once you have found out what direction to go in, head North until you leave the Prison boundary, and then start running in the direction. You will be attacked a lot, and if you wander about for too long, a man in a Chocobo driven coach will come and pick you up.
After a lot of wandering about, you should eventually come to another part of the prison where you will find Dyne.
After Barret has defeated Dyne, you will be returned to the main prison. You should now ask the man in the silver coach about how to leave the jail, he will tell you that the only way to get a pardon is to win a Chocobo Race.
Cloud will now find himself back in the Gold Saucer, where Chocobo Racing should be explained to you. There is a Red Summon Materia in this room, Ramuh, so make sure you pick it up before you start the race, as you cannot pick it up once you leave the room.
See my Chocobo Guide for more information on racing Chocobos, but your best bet for this race is to leave the controls on Automatic, and hold down R1+R2 (this will keep the Stamina Gauge up).
If you win the race you will be released from Prison, and you will get a Buggy as a prize. You can use this buggy to get to Gongaga, head south.
When you find him, Barret has to face Dyne on his own.