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.