There's not a lot of exploration to do in Corel Prison, so just head south and find Barret to figure out what the heck's going on. He'll tell you the about what happened, and who could of done it. First, go south to pay your respects to Mr. Coates. Then, the only thing you can do is go north to find Dyne. On the way there, watch out for the enemies who mug you. If they steal something, you must kill them immediately, or they'll vanish, taking your item with them. Before you meet up with him, though, you might want to get the Enemy Skill Laser from the Death Claw enemies who hang around the little car graveyard (you can also steal Double AP Armor, Platinum Bangles, from them). The Bull Motors have Matra Magic, too, if you missed it before. When you're ready, head north from the car dump to meet Dyne.
Barret has to fight this dude alone, so load him up with all the good materia, and make sure he's healthy. Dyne's not hard to beat, but watch out for his "Molotov Cocktail" attack. It can get you if your HP is low. Then, after he's dead, go back down to the trailer and have chat with Mr. Coates. He'll reluctantly allow Cloud to go up to compete in the Chocobo Races. This part is pretty easy, and also a lot of fun. The Ramuh materia is hanging around in the jockies' lounge, so make sure you grab it before the race begins. It doesn't matter how many tries to takes to win the race, as the result is the same, no matter what. However, if you want to win on the first try, try holding down R1+R2 as you race. It'll slowly refill your stamina bar (this trick can also be used later if you breed and race your own chocobos). When you've finally won, you'll get the buggy, your first vehicle! Have fun! Btw, if you hang around in the desert for a bit, you'll eventually find the enemy called a "Harpy." It can teach you the "Aqualung" Enemy Skill, which is really powerful this early in the game.