Upon leaving the Gym, you'll run into your rival. He'll direct you to the Canalave Library, where you'll find Prof. Rowan and his assistant waiting on the third floor. He'll talk about the Mirage Pokemon and have each trainer go to a certain lake. He'll have you go to Lake Valor. Fastest way to get there is to fly to Pastoria City, heal, then head east. Go through the route like before to reach Valor Lakefront, where you'll find the entrance to Lake Valor, and it isn't being blocked by the Galactic goons this time, so enter.
When you enter, you'll see that the lake has been completely demolished. Talk to the Grunt standing there. He'll explain how he's going to move on to Lake Verity next, but don't go there yet. Go to the center of the lake first to face the Galactic Commander: Saturn.
This battle shouldn't be any problem as long as you have a Dark and Psychic type Pokemon. Use a Dark type first to take out Kadabra, then when he uses Toxicroak, send out a Psychic type to take it out with hopefully little trouble.
After you defeat Saturn, he'll talk about Commander Mars being at Lake Verity, so that's where you want to head to now. Fly to Twinleaf Town, heal at your house, then head north. On Route 201, head left then up to reach Lake Verity.
When you enter, you'll see Prof. and his Assistant having trouble with Team Galactic. Take care of the Grunts then prepare to face off against Commander Mars.
Golbat won't be much problem if you have an Electric type on your team. Bronzor can always be taken out easily with a Fire type. Purugly might be some trouble though. It's holding a Sitrus Berry, so either defeat it as quickly as you can, or use Pluck to steal the berry, and take it out with a strong Fighting type
After defeating Mars, you will now be directed to Lake Acuity. To get there, you'll need to go through Mt. Coronet. Before going though, make sure you have a Pokemon with Strength and Defog. Now, fly to Celestic Town, heal if you need to, then head west of town to reach Route 211. From there, keep heading west to reach Mt. Coronet.
From the entrance, go up and use Strength to move the boulder. After that, keep heading up then head left to go into the next area. Here, you'll have to use Defog so you can see. After that, head left then go all the way up, then right to reach another set of stairs. Here, go right, up, then left to exit the cave. Now you'll be on Route 216.
This area is pretty straight forward. There's a set of stairs that you can follow to get an Ice Heal, or you can just go straight through. Heal at the house if you need to, then go north to reach Route 217.
This area can be annoying, because there is a lot of snow that makes it hard to walk and and the hail doesn't help either. Go straight up until you see some trees to the left of you. After you pass them, stay to the left and go up until you reach a house. Talk to the man inside who will explain that he lost his HM outside. The HM is right behind his house. Obtain the HM (Rock Climb), and return to the house. The man will let you keep the HM, and he will give you an Icicle Plate to go with it. Exit the house, and continue on north and you will eventually reach Acuity Lakefront.
When you try to enter Lake Acuity, you'll be denied by Team Galactic. You can't enter until you get the Icicle Badge, so ignore them for now and head east to reach Snowpoint City, where you'll be able to obtain the Icicle Badge.
There's not much to do here, so just heal up and you can take on the Gym immediately after, so enter the Gym. You'll find the main puzzle in this Gym is to destroy snowballs around to stop you from sliding. The main goal is to clear a path straight in the middle so you can slide right to the Gym Leader. To do this, gain speed by sliding from a high level and you'll bust through the snowballs. Good luck doing that. If you managed to solve the puzzle, you'll take on Candice, the Gym Leader of Snowpoint City.
You'll want a strong Fire type, because it will take out Candice's Snover and Abomasnow with very little trouble. Take care with Medicham, and use a Flying type Pokemon against it.
After you defeat Candice, you will be awarded the Icicle Badge, which will allow you to use HM08 (Rock Climb) outside of battle. She will also give you TM72 (Avalanche), which doubles in power if the user is damaged before it attacks.