Part I: Mog
Head to Narshe. Just for reference, Narshe is on the top middle area of the map, the little cave that should look familiar. Go around to the west to go in the secret entrance and retrace the path you took earlier in the game. Go in the cave opening leading to moogle sanctuary to find Mog sitting there by himself. He'll rejoin your party and tell you of a sasquatch hiding up in the mountains. After he leaves or joins your group move forward and search the ground he was standing on to get a moogle charm, a relic which allows you to eliminate all random encounters.
What you do next depends upon your overall strategy. Since Umaro only requires leveling up and can't be taught any spells, you may prefer to have him join your group later, since his level begins at the average level of the party. If you have three people in your party when you meet Mog he'll join your group, otherwise it's fairly simple to just leave Narshe and trade out your party. If you want Umaro now, put Mog in your party, otherwise come back with him later. Keep traveling along the path to reach the back of the house in Narshe where you began the game and exit to go into the main village of Narshe. It's worth mentioning that you can come back here later in the game with Locke to clean the place out, but that is listed under Locke's sidequests.
Part II: Ice Dragon/Tritoch
Go north through the mountains of Narshe and keep following the path until you get to the snowy field where you fought Kefka. This is the only place Mog can learn the Snowmann Jazz dance so make sure he does when you take him here to get Umaro in your party. There will be an ice dragon wandering through the paths and a save point in the usual position. Save, then prepare to take on the ice dragon.
Equip ice shields or anything resistant to ice magic if you want and use your strongest fire spells, healing in turn. The Ice Dragon is vulnerable to multiple status effects, including Poison, Silence, Berserk, Confuse, and Slow. Some of your characters can randomly be frozen by the N. Cross attack, but you can cast fire on them to thaw them out for low damage. Eventually it should give.
Be prepared for Tritoch to attack you when you talk to him at his usual spot on the north of the cliff. Use your strongest fire magic against it (Fire2 might actually be stronger than Flare) once again with your strongest spellcasters. It will eventually melt and you'll have the most powerful ice/bolt/fire magic ready to be learned.
Part III: Umaro
After you beat Tritoch an opening behind the cliff will open up. Avoid the dark patches while going towards the left path to get a tough monster in a box fight against some pugs. The right path leads to a pit pretty fast, so try the middle path to get an x-ether in a chest. When you want to move on fall in a pit or just go down the stairs. Go to the bottom right corner in the next area for a gauntlet, and climb the stairs to the bottom right and walk over the walkway to another set of stairs. Don't flip the first switch in the next area unless you want to fall down. Flip the second switch to fall into Umaro's cave. Pull a piece of magicite out of the skull to challenge the big yeti himself.
Like all the bosses in this area Umaro is weak against fire. Use your strongest fire magic and don't let up. If Mog is in your party, talk to Umaro afterwards and he'll join you. Go North and you'll be dropped out of the cave entrance you might have seen Umaro peeking his head out of earlier. Head right and keep following the path to leave the caves and go south to exit Narshe.