This article is from the Final-Fantasy and other Square Soft Games FAQ, by email@example.com (Nick Zitzmann) with numerous contributions by others.
Celes: Just start the game!
Cyan: Mt. Zozo
Gau: Anywhere on the Veldt (you must have a party of 3)
Relm: Cave on the Veldt*** and/or Jidoor
Shadow: If he's not in the Cave on the Veldt****, he's dead...
Strago: Fanatics' Tower*****
Locke: Phoenix Cave
Banon: He seems to have disappeared, don't worry about him.
* = Terra will not join the party until Phunbaba is defeated. Your party
must confront Phunbaba twice - once to scare him off, and then return to
Mobliz later in the game to destroy him.
** = You'll meet up with Edgar in Nikeah, but he won't join the party
until you reach Figaro Castle.
*** = In this scenario, you must rescue Relm from the Cave, but she will
not join the party until Chadarnook is defeated in Jidoor.
**** = In this scenario, you must rescue Shadow from the Cave, but he
will not join the party unless you bet the Striker at the Colosseum.
***** = Strago will not join the party unless Relm is in the current