Your first chance to get Mog happens after you visit the southern continent and deal with the Empire a little bit. You'll finally have full control of the airship and can return to Narshe.

Go to the house on the far right of the town where the old man keeps his treasures. If you visited before, you know one of the treasures was "locked". You'll encounter Lone Wolf the Pickpocket who has stolen this treasure and you will chase him around Narshe and the Mines. Finally you will corner him in the area by the Frozen Esper and he'll have Mog as hostage. You basically have to choose between Mog or a Gold Hairpin item. Mog can be acquired later but its much later. Also if you are playing any version of VI that's isn't the GBA version, Mog will never be able to acquire one of his Dances if you choose the Gold Hairpin over him.

Hope this helps without too many spoilers.