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).