Zarghidas also known as Sal Ghidos the Trade City which you must beat Besselat Fort to unlock and you must have already gotten Worker/Construction 8, once your in Sal Ghidos you get the scene of Ramza walking and then talking to a flower girl(Aeris). you MUST buy a flower to get cloud. After that you need to go back to Goug and there will be a scene that shows you a new machine reacting to the Aerucite.

You must go back to Zeltennia and read the Rumours then there will be a isle unlocked above Zeltennia, beat the fight and then go back to Goug, Cloud will come from a time rip or w/e and then you'll have another fight at Zarghidas, you'll come to a scene where Cloud talks to Aeris for a bit and then walks off and then Aeris is confronted by Knaves and after you win the fight (you need to protect cloud) then you'll have cloud in your party.