How to get all the NPCs
As you know, you can get a lot of characters in Final Fantasy Tactics. You'll get Agrias, Mustiado, and Orlandu automatically, but some you have to go out of your way to get. Believe me, it's well worth it. The following will tell you what do to get Worker 8, Beowulf, Reis, and...Cloud! Please note that you must Mustadio in your party at all times, so don't dismiss him or let him get killed! He is essential to your party. The other thing is that when you were in Zarghidas City, you must have bought a flower that costed 1 gil from a flower girl. If you didn't, you just missed out on Cloud.
You can get Cloud anytime after you defeat Adramelk. First, go to Goug Machine City, where Mustadio's father will show you a steel ball he's found. If you've already done this, you don't need to do this again.
Next, go to Goland Coal City, which is in the center of the map. Go to the bar there and listen to the rumor "Ghosts of Colliery". Now leave. After you're outside, nothing will happen, yet. Go to Lesalia, the city right above Goland. Ramza will go into the bar and learn more about this monster. Agree to take the job, and on your way out, a knight named Beowulf will ask you if he can join or not. Say yes, and he joins as a guest for now.
Notice now that Goland Coal City is red. I would suggest going back to Lesalia and getting some better equipment for Beowulf, and if necessary, for your party. Equip Ying-Yang Magic as Beowulf's secondary skill, since he has a lot of them learned. Save before going in. You'll get 3 underground battles before getting to the sewers where Reis is. The underground battles really don't look "underground", do they? If you want help in the battles, click here.
When you do get to sewers, you'll see that a Holy Dragon is being attacked by some monsters. You get to save her. How typical, huh? Reis is not a bad fighter, and her attacks are powerful. Beowulf also joins in, and this battle shouldn't be that much of a problem. When the battle's over, you get the Aquarius Zodiac stone.
Well, wasn't that fun? Return to Goug. Put the Aquarius stone into the steel ball and Worker 8 is born! A very comical scene will follow, and Worker 8 will join you. You just got your first NPC. Feels great, doesn't it? On the way out, Mustadio's father will show you something else he found, and says he needs another Zodiac stone.
Get ready for some long journeys and many random battles. Now, you get to go to...Zeltennia Castle. Yep, all the way up there in the top right hand corner. Fun, huh? Go to the bar and listen to the rumor "Cursed Island, Nelveska". A new path will open up to the Island. Get someone with a high jump ability and give them the skill Move-Find Item. You can get some extremely good items here. This will be one of the hardest battles you'll ever get. This might even be on the same level as the battle with Wiegraf. Anyway, you'll meet...Worker 7! He's powered by the Cancer Zodiac stone. Worker 7 will attack you along with his "friends", and he will come back to life with 1 HP after you've knocked him out. After you beat him, he'll leave behind the Cancer Zodiac stone. Just as you're about to leave the island, Beowulf will use the stone to transform Reis back into human.
Now, go all the way back to Goug(Don't you wish it was closer to Zeltennia?). Mustadio's father will power up the weathervane with the newly accumulated Cancer Zodiac stone. Now pops out....Cloud! He doesn't join you just yet, and runs off in search of Sephiroth.
Now, you get to go all the way back to Zarghidas City. Don't you just love the long trips and many random battles? You'll meet up with Aeris, the flower girl, and this time, she's being attacked by a bunch of thieves. Cloud comes in at this moment, trying to save her, and you get there at the same moment, too. Your job is to protect Cloud, and this battle's a piece of cake. Afterwards, Cloud will join!
You'll first notice that Cloud can't use his limit breaks. You need the special one-of-a-kind Materia Blade. The sword is found in Bervenia Volcano. Equip someone with the Move-Find Item, and start a random battle there. Get that someone to the highest point of the battlefield and you should have no trouble finding it. Now, Cloud can use his limit breaks. You'll spend a lot of time leveling him up, though, considering he starts at level 1 when you first get him.