It is on Route 134
You will need to find a way to get into the dive spot where you can obviously use dive.
Once you go under, speak(?) to the braille and dive up
After that, go straight and speak(?) to the braille and use cut on the braille. A door will open.
Go inside, and keep going straight. Once you reach the braille again, use dig. That will unlock the chambers to the regis
Keep in mind that you need these Pokemon and items:
Relicanth in the front of your party
Wailord in the back(or vice versa)
A Pokemon with Cut and Dig(I would use nincada)
For the Regis:
Regirock: Go to the desert on Route 111. go all the way down. You should see a cave. go inside and go straight. Go down 2 squares(?) and left 2 squares. Use strength. A door will open and you will be able to catch regirock. If you go down 2 and move left 2 and it doesn't work, try starting over and go down 2 and right 2
Registeel: This one is really easy. Just go to Route 120 and find the chamber. Go to the very center of the chamber and have a Pokemon use fly. The door will open and there is Registeel
Regice: This one requires patience. On route 105 you will see a structure exactly like Regirocks and Registeels. Go inside, and run clockwise staying next to the walls. once you reach the exit. just wait 2-3 minutes without moving and after that the door to regice is open.
Regigigas: After catching all the regis, have them in your party and go to island cave(where you catch regice). But before that, go to pacifidlog town and speak to a little girl in one of the houses she will mention something about an icy related item. The items are NeverMeltIce, Casteliacone, and Snowball. Have regice hold one of them, and go to island cave. There will be an "earthquake" and regigigas will appear. make sure you have all the regis in your party and give regice a nickname.
Whew, that took a while.
Hope I helped!