Quote Originally Posted by Teh Lavos
I thought Dyne had been down there ever since he (SPOILER)Fell off the cliff, and lost his arm.

Which would explain why he was the boss. He would have been able to kill anybody that stood in his way, so people would have got scared of him and decided to make him the 'boss'.
No, that doesn't work. Dyne fell near North Corel, which is separate and located some distance from Corel (which became the Desert Prison after it was partially reclaimed by desert). In any case, Dyne saw the same doctor Barret did, as Barret was aware of another individual getting the gun-grafting surgery.

Barret: There's another... another man that got a gun grafted inta one of his
arms. It was four years ago...
Recall the scene in the past, where we see Scarlet and the Shinra troops firing at Barret and Dyne. Dyne stumbles, almost falls, but Barret grabs him by the arm. Soon, however, the gunfire strikes Barret's arm, and Dyne falls.

Barret: From then on, I couldn't use my right arm no more. ...I was depressed
for a while. But then I threw away my artificial arm and got this gun grafted
in.
Got a new right arm to get revenge on the Shinra, who took everything away...
Back then, I heard the doc say there was another man who got the same operation
as me. But, his was the left arm.
As to the initial question:

How exactly Dyne ends up in the Desert Prison is unknown. Since the Desert Prison is Corel, however, it's completely understandable that he retains a connection to the location. Given his obvious and dangerous instability, it's also not surprising that Dyne could have risen to the boss position. Finally, while the specifics are not explicated, it is alluded to that Dyne may have had certain freedom of movement unavailable to others trapped there.

Cloud: Where are we?

Cait Sith: A desert prison... Corel Prison...

Cloud: A desert prison?

Cait Sith: Yup, a natural prison in the middle of the desert...surrounded
entirely by quicksand. I heard that once you get in, you never get out... But,
there was one special exception...
While the special exception could refer to the chocobo jockey exemption, I don't think that is what this segment of dialogue implies. My view is that Dyne had been established as the boss for some time before he killed the people in the Gold Saucer. It also seems unlikely that Dio was fully aware, if at all, of Dyne.