This depends solely on the game that you are playing. In the third generation games, the "Regis" are located at three separate secret locations that can only be unlocked by doing the puzzles in an underwater cave directly west of Pacifidlog Town. The puzzles are all coded in Brail, so I recommend checking bulbapedia.bulbagarden.net to help you out. Just search the "Sealed Chamber". Once you unlock the secret locations, it is just a matter of traveling to the locations, solve another puzzle, and then catch your prize.
If you are playing on Pokemon Platinum, catching the legendary golem trio is a bit different. You will be able to find the lair to each one only after obtaining Regigias, either through a special event or by using the Action Replay.