We consider the joint constellation design problem for the two-user non-coherent multiple-access channel (MAC). Based on an analysis on the non-coherent maximum-likelihood (ML) detection error, we propose novel design criteria so as to minimize the error probability. Based on these criteria, we propose a simple and efficient construction consisting in partitioning a single-user constellation. Numerical results show that our proposed metrics are meaningful, and can be used as objectives to generate constellations through numerical optimization that perform better than other schemes for the same transmission rate and power.