Follow the old man's advice and head west across the bridge behind his house. You'll soon find yourself in another mine, separate from the one you were just in.
Terra's Morph Command isn't initially available, but it's a powerful option once it is, doubling her damage output as well as her defense against magic for a time.
Narhshe West Mine
The encounters here are the same as the ones you saw after defeating Whelk, but now you only have Terra and you no longer have MagiTek armor to rely on. Fire can be used to end any battles quickly, though Terra has limited MP and may need some for Cure spells. Fortunately you won't have to go very far. There is a save point up ahead, and you can always use a Sleeping Bag to restore Terra's MP.
There are two chests here which represent an interesting mechanic: their contents change depending on when you get them. Right now, the first chest contains a Fenix Down and the second a Sleeping Bag, but far later in the game (in the World of Ruin) they will contain a super-rare Pod Bracelet and an Elixir, respectively. Given the relatively common nature of the treasures available right now, it's advisable to wait to open these chests.
The path splits after the chests, though the left branch quickly ends. At the north end of the right branch, the Narshe guards will catch up with Terra, who will fall to the level below. This leads to a cutscene, after which you will find yourself back at the old man's house where you will meet a new character.
Locke
You will be given the chance to name Locke, after which the old man will fill him in on the situation. He needs to rescue Terra before the Narshe guards get to her. Fortunately, he will find her all on his own, so you won't have to fight through the same area for a second time.
When Locke arrives on the scene, the Narshe Marshal appears with a group of monsters at his disposal. Locke looks outgunned, but fortunately a bunch of Moogles come to Terra's rescue. It's time for one of FFVI's most interesting mechanics: party switching!
Protecting Terra
You will suddenly be controlling three separate parties that you can swap between (outside of combat) with . The first party consists of Locke and three Moogles. The other two parties consist of four Moogles each, but Mog is the leader of party #2. He's quite a bit stronger than the other Moogles, and will learn the Dusk Requium dance if he engages in combat here. You can even steal his Mithril Pike and Mithril Shld to enhance your permanent party members' gear early in the game, though you have to defeat the Marshal with him so unequipped to complete the sequence.
Your top priority here is to make sure none of the wandering beasts reach Terra. You can deploy your party in a defensive array, clogging up all the chokepoints to prevent this. Every wandering beast represents an Vomammoth, Lobo encounter. While you've seen both of these enemies before, they are now capable of using new attacks that are far more dangerous. The Vomammoth's Blizzard in particular will quickly drain a party of its HP, dealing around 40 damage to each party member per use. This can be countered by switching parties when one gets low. There are only six wandering monsters, so you should be able to take them all out while keeping one party relatively fresh for the Marshal.
An alternate plan is to leave two parties behind to protect Terra while the third rushes the Marshal. You'll fight less encounters this way, but it can make for a tough fight depending on how many encounters you have along the way. You probably have gotten a lot of Tonics and Potions as monster drops (or by using Steal during this sequence) up until this point, so they can be useful here since no one in any party has any inherent healing ability.
The Marshal
However you decide to handle this sequence, it ends when you defeat the Marshal. He has a pair of Lobos with him. Take them out quickly, because as long as they're around, the Marshal may use his Stop-inducing Net attack. Of course, once they're gone he will instead use a double-damage Charge attack. Either way, you will have to be cautious.
The decision of which party to fight the Marshal with can be tough. You probably don't want to use your non-Mog Moogle party. Using Locke allows you to steal a MithrilKnife, which is a decent upgrade over his Dirk. Mog, on the other hand, can use Dusk Requium which can take out the Marshal in one blow with Snare if you're lucky, and is generally quite effective even if Mog uses other moves.
The good news is that there's not much danger in losing here. If a party is defeated by the Marshal or any other enemy, they will re-appear behind Terra with every party member's HP set to 1. You're probably not going to have much luck if every party is defeated, but there's no great harm in trying to steal that MithrilKnife even if Locke's party may not be up to the task of actually defeating the Marshal. Like all bosses, the Marshal offers no experience points, so there's not much to worry about there either.
Leaving Narshe
Once the Marshal is done for, you'll see a short scene after which the party will consist of Locke and Terra, both with their HP and (in Terra's case) MP restored. You can leave Narshe now, but first it's worth exploring the nearby Narshe Classroom to find a few minor items (a Tincture, a Sleeping Bag, and a Tonic) and a lot of information about how the game works. You'll be chased off if you try to re-enter the town proper, so for now head south, outside of town.