I would definitely do this with arrays.
Each Row would have a World/Stage code. For example, "W1S1" could be world 1 stage one.
Then there would be two columns: Unlocked and Replay. They would all be set to zero.
As players complete stages, it would change the array. Completing World 1 Stage 1 would change the W1S2 Unlocked value to 1.
Defeating a midboss would change the appropriate Replay values to 1. Defeating midboss 1 would change the Replay value for W1S1 and W1S2 to 1.
Defeating World 1's final boss would change the Unlocked and Replay values for W1S1, W1S2, W1S3, W1S4, and W1S5 to 1. It would also change the Unlocked value for W2S1 to 1 as well (since that's the first stage in the next world).
Finally, the World Map (or stage select screen, etc) would reflect the current state of the array. For example, stages with an Unlocked value of 0 could be drawn at 50% opacity or in greyscale, and stages that have a Replay value of 0 could have a little lock icon.
Is that what you're looking for? You could do also this with dictionary entries, if it's more comfortable (just more typing).
Yeah, I figured it was going to come down to arrays.
One of the issues I had with looking arrays over was I never found a list of tutorials that would explain how arrays could be used for multiple separate things in one project; kind of like how you just have separate event sheets.
I just quickly found a YouTube tutorial on using an array for a weapon inventory and I'm going to follow that while integrating your World Unlock/Replay concept. I wouldn't have thought of 2 separate values for this but it makes sense. Maybe when I'm done I can get a Hi-Score array working as well.