Evolutionary therapies hold great promise to ameliorate cancer outcomes, but cells also escape treatment by non-genetic means, such as through reversible, plastic cell state transitions. Epithelial-mesenchymal transition (EMT) is an example of such plasticity: cancer cells have co-opted this developmental transition to evade treatment and to seed metastases. By characterizing the gene regulation underlying EMT, we can discover means to control the spread and progression of cancer. We have developed methods to identify marker genes of highly metastatic EMT intermediate cells via mathematical modeling constrained by single-cell RNA sequencing data. Across multiple tumor types and stimuli, we identified genes consistently upregulated in EMT intermediate states, many previously unrecognized as EMT markers. We also study the gene regulatory network dynamics of EMT to understand the impact of network logic on the transition paths across the EMT landscape. We discover that choice of logic (multiplicative vs. additive gene regulation) profoundly impacts EMT phenotypes and leads to opposing predictions regarding factors that control EMT transition paths. We show that strong inhibition of miR-200 destabilizes the epithelial state and initiates EMT for multiplicative logic, in agreement with experimental data. Using single-cell data, stochastic simulations and perturbation analysis, we show how these results can be used to design experiments to infer EMT network logic in live cells. Integration of plasticity phenotypes into models of tumor evolution will provide a richer picture of the myriad ways cancer cells attempt to evade our best defenses.