Part I, Finding Shadow/Relm
If you waited for Shadow on the floating island and managed to take him away with you, you'll find Shadow in a cave on the Veldt. If you didn't you'll find Relm there, but for the purposes of this part I'll assume you're looking for Shadow.
Head to the cave on the Veldt. For reference the Veldt is on the northeast area of the map, southwest of the little triangular island where the zoneeaters live. You'll meet Interceptor on your way in. The path is fairly straightforward, make sure to grab the rage ring for Umaro as you pass by the peasants around the fire, and find a hidden passage to the left after going through the door to have a monster in a box fight. The monster is weak against fire (for your information use holy water for one hit ko), and gives you a weapon for Sabin. Flip a switch in the next room, and make sure you go to the bottom of the room to get the striker, it's Shadow's best weapon and you'll need it to have him join your party. Go through the passage you opened and up and around into a room with a save point, and head into the next room for a boss fight with Sr. Behemoth.
Sr. Behemoth is weak against fire. Use the strongest fire magic you have available and heal when necessary and you should be fine. After you beat him the first time his ghost will appear and attack you from behind, use a revivify on him to kill him in one shot, or you can use cure or life spells to finish him off or just nail him with some more fire magic. When you finish you'll take Shadow over to Thamasa to recover. You'll see the last of his dreams chronologically, and witness him leaving Thamasa with interceptor, leaving a girl behind saying he wants to make it a safe world for them to grow up in.
Part II, Getting Shadow in your party
This is pretty simple. Just go to the Coliseum at the north west of the world map and bet the Striker. Just use a high-level character to fight Shadow, it should be pretty easy. You'll win the Striker back and Shadow will join your party.
Part III, Shadow's Dreams
Stay in an inn with Shadow in your party and he'll randomly have dreams explaining some of his history.
- In the first dream, he'll see a man named Baram calling to him, Clyde, for help, saying he's done for
- The second dream will reveal Baram and Clyde as great train robbers who just got away with stealing a million GP. They'll name their group the Shadow Bandits.
- In the third dream, Baram will be badly wounded and Clyde is trying to carry him to town. Baram says for Clyde to leave him behind, Clyde refuses but finally gives in. Baram asks Clyde to kill him so he won't be interrogated, but Clyde is unwilling to, so he runs away.
- In the fourth dream, you see Clyde waking up in Thamasa, badly injured, with a woman taking care of him and a dog running up to greet him.
- The fifth and final dream takes place when you rescue Shadow from the cave on the Veldt. It shows him leaving Thamasa with Interceptor and leaving a girl behind.
You can conclude from the dreams that Shadow was Clyde Arrowny, Relm's father, and that Relm's mother may have died in childbirth. Keep in mind you can receive four of the dreams in the World of Balance as well.
Also, the facts that Interceptor acts as if Relm is no stranger, and you can equip the 'Safety Ring' ('Memento Ring' in the SNES version) to either Relm or Shadow (the description reads, "Mother's love protects from fatal magic attacks') make this connection clear. If you leave Shadow behind on the Floating Continent, Relm will have a dream instead.