We present a socially assistive robot (SAR) system designed to engage elderly users in simple physical exercises. The role of physical embodiment in our exercise system is explored with a large multi-session user study comparing the effectiveness of a physically embodied robot coach to that of a virtually embodied robot coach (a computer simulation of the same robot). The study also illustrates the effects across the age range, as half of the study was conducted with older adults (n=33) and the other half with young adults (n=33). The results of both studies are presented; they show a strong user preference for the physical robot embodiment over the virtual robot, demonstrate the positive effect that physical embodiment has on participant evaluations of the enjoyment and usefulness of the interaction and of the robot in terms of helpfulness, social attraction, and social presence. In addition, the high overall participant ratings of the interaction and robot in the studies demonstrate the viability and usefulness of the SAR system in motivating exercise among elderly users.