First you have to have some Pokemon that know HM03 Surf, HM08 Dive and TMDig. Fly to Paciflog town. Go in the Pokemon Center and withdraw Wailord (evolution of waimer) and Relicanth (If you don't have these Pokemon yet catch a waimer with your super rod in the water near Mossdeap city.)
They are near Lv.35 so you have to train it to Lv.40 for it to evolve. Catch Relicanth underwater to the left of Mossdeap City. He is rare so have patience. Surf left and always stay on the bottom currents.
After you get to the 3rd or 4th square of land, you'll see the deep water. Dive in. Walk all the way to the top. Use Dig. Go through the door and go all the way to the top and read the words. Then press A again and all of the 3 doors (for the 3 regi's) will open. You probably already passed them before.