There's a fairly rough bridge over a stream that's almosty completely frozen over. Almost. Walk down to a thawed section of it and press 'O'. Cloud should dip his hand in and say "Ah, a hot spring" or something. The Snow Woman's cave is in the east. Not sure if it's marked on the map... I think that only the cave through which you can exit is marked on the map.
Snow's cave is near a crossroads where several paths intersect.

If you think that's tough, try finding the 'Added Cut' materia, also cunningly hidden on the Great Glacier. That one took me forever.