Depending on which way you went when the course split on the Snowboarding Trails, you'll land in a particular spot in Ice Gate. If you went left twice, you'll land in the forest; if you went left, then right, you'll land by the southern entrance to Ice Gate; right then left will get you by the tree in the middle of the map; and right both times will land you by the little eastern cave that has only an exit to the outside world in it. If you're depending on this walkthrough, I would suggest trying to end up by the tree.
Now, it's very easy to get confused here, although once you've explored for a while, you should be able to get the feel for the layout of the place. Nonetheless, it's still pretty tough to figure out where you're supposed to be going. In order to get all the important treasures, try this: From the tree, go right, then from there take the path leading up. On the second screen, look in an outcropping of rocks on the right side of the trail to find the "Added Cut" materia. It's easy to miss, but if you look at the rocks (press the O button) you should find it. Pick it up and continue northwest, and you'll find yourself at a Hot Spring. Go down to the water's edge and touch the spring. From there go straigh north, and you should eventually wind up on a big tundra. Go north until you find the cave with the "Enemy-All" in it (make sure you use your markers, and stop when the wind starts blowing so that you don't lose your way), then go straight right, and you should evenually run into snowy path leading right. Follow until you reach a rocky spot with a cave. In the cave is a witch that won't like the fact that you touched the hot spring. Fight her, and receive the Alexander Summon materia. You can then go back to the left to get to the ice fields again, where going a little left and then north will hopefully get you to the base of Gaea's Cliff. Or, if you'd rather, do a little exploring throughout the rest of the Ice Gate. On the fields is that cave with another All materia in it, and there are some other mildly exciting things hanging around back in the other areas of the map. Eventually, however, you will succumb to the cold, and fall over. Don't worry about it; help is close by.
If you found it on your own, you'll arrive at the base camp, cold, but consious. If you passed out from cold, the man running the base camp will find you and bring you in. The man here will then offer to let you rest there when ever you want and tell you how to climb the mountain. From there, you can save, make up a relatively strong party, and get yourself ready to climb Gaea's Cliff.