Regice, Regirock, and Registeel
You also have to defeat the Elite Four to capture these three Pokemon. Additionally, you will also need a Relicanth, Wailord, a Pokemon with Surf, Dig, and Fly. You'll need all of those to unlock the caves in which the Regis rest.
Save often in case you get lost.
Go to Pacifidlog Town and go into the water to the west. Surf all the way down and once you hit the bottom go west and stay as close to the bottom as possible. Go into the water current to be carried to an island where a Blackbelt trainer should be. Go to the top left corner of this island, as top as possible. From there, surf left.
You should be carried to an island with a pool of surfable water in somewhere the middle. Go to the top left corner of this island, as left as possible and surf to the left. You should get taken around an area of rocks. Once you stop, surf up and you should see two girls. From the girls, surf left until you can walk. walk around the rocks to the bottom left corner of the shallow island, as bottom as possible. Then surf left once again.
PAY CAREFUL ATTENTION HERE.
Once you land, walk straight across and surf again until you come to a small patch of dark blue water you can dive in. It is VERY small patch of deep water so PAY ATTENTION. Dive in down into the water and enter the cave.
Go down until you reach a rock with writing on it. From the middle of the writing, go back up to the surface where you should come across a bunch of rocks with more writing on them. Walk to the very back(top) of the room and read the writing, which says "Dig here". So dig. Enter the new cave.
Go to a rock in the middle of the back of the cave with writing on it. It says "First comes Relicanth. Last comes Wailord". Put your Relicanth in the front of your party and Wailord in the last slot. Now read the writing again. You should hear an earthquake and three doors opening. You can now find the three Regis.