Getting There
Fly to Mauville. Go up to the desert near the Winstrait family (Victor, Vivian, Vivi, and Victoria) where you need the Go-Go Goggles. Go to the middle-bottom of the desert where you should see the same form of rocks as where Registeel was. Go into the open rock in the middle and save. Go to the back of the room, then go right, right, down, down and use Strength. The door behind you should open, if it does not then do got back to the end of the room and go right, right, right, down, down and use Strength. Once you go inside the door, Regirock will be in the same position as Registeel. SAVE NOW! Go up to it and battle!Good luck!
A Hint for a Strategy You Could Use...
Putting it to sleep is good, your Relicanth should know Yawn, but it will wake up!
My Battle Status
Pokemon I Used to Capture Regirock (battling):
Relicanth, Level 32: Water Gun, Yawn, Take Down, Rock Tomb
Togetic, Level 77 (Colosseum): Metronome, Psychic, Wish, Fly
Flygon, Level 75 (Colosseum): Crunch, Earthquake, Strength, Dragon Claw (used for stalling)
Chimecho, Level 28: Confusion, Psychic, Take Down, Yawn
Pokemon Not in Battle (in party):
Rayquaza, Typhlosion
Captured With: an UltraBall after about 5 tries
Capture Rating: 1 2 3 4 5 6 7 8 9 10 9 - Easier than Registeel, but still very hard
Time (that I) Needed for Capture: about 20 minutes
Condition: 1 HP left and asleep
Back to Registeel
Forward to Regice
Back to Unlocking the Regies