The recent discovery of shape memory behavior in Mg-Sc alloys has opened the door to the possibility of lightweight shape memory alloys. Very little is known, however, about martensitic phase transformations or about equilibrium phase stability in this alloy system. Here we report on a first-principles statistical mechanics study of zero Kelvin and finite temperature phase stability of hcp, bcc, and fcc based phases in the Mg-Sc binary. Our calculations reveal a rich array of phase transitions among the different low-temperature ordered and high-temperature disordered phases. Ground state orderings on hcp, bcc, and fcc belong to families of hierarchical structures containing rods of scandium atoms assembled in layers that repeat periodically. Both fcc and bcc are found to undergo a series of second-order phase transformations with increasing temperature until they completely disorder. A high degree of degeneracy is predicted at low and high temperatures among hcp, bcc, and fcc, a property that is likely to play an important role in the shape memory effects observed in this alloy.