The Regi trio have got the same legwork to activate. Before the three locations become available to you you must have a Relicanth and Wailord as well as a Pokemon with Dig and Dive. On Route 134 you must take the correct path through the currents to the patch of water you can Dive in. Once below folow the path up to the Braille inscription and resurface. Go to the next inscription and use Dig. Make Relicanth the 1st of your party and Wailord the 6th, then read that inscription. Three earthquakes will trigger and open passages on each respective route.
Regirock is found in the Desert Tomb, which is at the bottom of the desert in Route 111. On the walls inside is a message like the ones on Route 134. Go right twice, down twice (best use the D-Pad for this) and then use Strength and the door to Regirock should appear.
Regice is found out in Island Cave, which is on a small reef on the west part Route 105, requiring Surf to gain access. Once inside, you will find a message in braille telling you to wait. After two minutes the door opens and Regice can be fought.
Registeel is the last of the three, found west of Lilycove in Route 120's Ancient Tomb. Use Fly in the middle of the room, and Registeel should appear.
Location: Island Cave
Once you have the three Regis, Regirock, Regice and Registeel, you can unlock Regigigas. The method to get this is rather complicated. In Pacifidlog Town, in the north-eastern house, a girl will tell you stories her grandfather told her. At random, she will tell you a part of the story about how to get Regigigas. This involves location and the other features. Take all three of the Pokémon to the Island Cave during the day, and make Regice hold a frozen item such as CasteliaCone, Snowball or Never-Melt Ice, and have Regice have a nickname, and Regigigas will challenge you.
Once you get the Good Rod, you can use it to catch Wailmer, which you can then evolve in Wailord. The Super Rod also enables you to catch Wailmer.
When diving, go through the grass. Underwater there are wild Relicanths. If you don't find one quickly, don't worry, as I believe they are rare.
•You also to have at least one Pokemon that knows dig and another that knows dive on your team.
• Save before legendaries
•Make sure to inflict a status condition as this increases the catch rate
•The best status condition when catching Pokemon are Sleep and Paralysation, although Paralyzation doesn't 'wear off' whereas Sleeping Pokemon can wake up.
•Preferably do not Poison or Burn the Pokemon, as they will faint from the status condition eventually.
•Stock up on Pokéballs.
•Ultra balls, Timer Balls and Dusk Balls are pretty useful.
•Use Heavy Balls if the Pokemon is heavy, Level Balls if the Pokemon is lower level than yours, etc.
Good Luck! :D