We use N-body simulations to test the dependence of cluster substructure on four cosmologies and three initial power spectra. Our purpose is to quantify the amount of substructure in each model and understand these results in terms of cluster merger histories as well as the behavior of the substructure statistics. In order to test the robustness of the statistics to observational effects, we perform our analysis not only using full three-dimensional information for each cluster, but also including projection and subsampling. We find that the statistic that best distinguishes the models is a very simple measure of gross deviations from symmetry in the projected mass distribution: the ''center-of-mass shift'' as a function of overdensity. The Dressler-Shectman and Lee-Fitchett statistics perform relatively poorly as cosmological indicators, even though they are quite sensitive to substructure. The substructure measured by these statistics relaxes in about a crossing time.