This page explains how to reunite with Locke Cole after you get separated from him in the World of Ruin.
Finding Locke
To get Locke again after you are separated in the World of Ruin, it's recommended to follow the walkthrough, starting with Solitary Island, but if you want to get Locke as soon as possible, you need to get an airship.
After you leave the Solitary Island, the first step to getting the airship is to go to Nikeah, which you can reach by going to the northeast part of the continent, where there is a narrow strip of land. Go northeast on that strip of land, and go as far to the north as you can on the thin part of the continent.
Follow the steps on the Nikeah page to get control of Figaro Castle, then use the castle to go to Kohlingen. The town of Kohlingen is northwest of the castle itself.
Then follow the steps on the Kohlingen page to get the airship.
Take the Airship to the middle of the south part of the world map, north of Tzen and Kefka's Tower. Land in the center of the star-shaped mountain range. This will lead you to Phoenix Cave, a difficult dungeon. After you complete this dungeon, you will be reunited with Locke.