The order of events, at least for the ps version (dunno if its altered for psp...), is ...
(SPOILER)
Visit Goug multiple times (must have mustadio alive), until his father points out a certain gem you need to operate the machine

Listen to the rumor about Monsters in Colliery at Goland Coal City
Go to Lesalia, agree to allow Beowulf help you, and go back to Goland and go through the battles

Now you have Beowulf and Reis, and you cannot continue the story until after Bethla. Go back to Goug, and Worker 8 Joins you. Leave and come back and he'll tell you about another stone you need. Go to Zeltennia and read the rumors about the island. Go there and beat Worker 7. Reis becomes human. Somewhere around this time period, you can meet Aeris in Zarghidas, buy a Flower. Return to Goug and Cloud will appear. After the battle at Igros, going to Zarghidas (which is right next to Zeltennia), and a battle will happen where you save Cloud.

And he joins you after