Metropolis-Monte Carlo algorithms are developed to analyze the strand separation transition in circular superhelical DNA molecules. Moves that randomize the locations of unpaired regions are required in order to diminish correlations among the sampled states. This approach enables accurate simulations to be performed in reasonable computational times. Sufficient conditions to guarantee the formal correctness of the complete algorithm are proven to hold. The computation time required scales at most quadratically with molecular length, and is approximately independent of linking difference. Techniques are developed to estimate the sample size and other calculation parameters needed to achieve a specified accuracy. When the results of Monte Carlo calculations that use shuffling operations are compared with those from statistical mechanical calculations, excellent agreement is found. The Monte Carlo methodology makes possible calculations of transition behavior in cases where alternative approaches are intractable, such as in long molecules under circumstances where several runs of open base pairs occur simultaneously. It also allows the analysis of transitions in cases where the base pair separation energies vary in complex manners, such as through near-neighbor interactions, or the presence of modified bases, abasic sites, or bound molecules.