We investigate the red supergiant (RSG) population of M31, obtaining radial velocities of 255 stars. These data substantiate membership of our photometrically-selected sample, demonstrating that Galactic foreground stars and extragalactic RSGs can be distinguished on the basis of B-V, V-R two-color diagrams. In addition, we use these spectra to measure effective temperatures and assign spectral types, deriving physical properties for 192 RSGs. Comparison with the solar-metallicity Geneva evolutionary tracks indicates astonishingly good agreement. The most luminous RSGs in M31 are likely evolved from 25-30 Mo stars, while the vast majority evolved from stars with initial masses of 20 Mo or less. There is an interesting bifurcation in the distribution of RSGs with effective temperatures that increases with higher luminosities, with one sequence consisting of early K-type supergiants, and with the other consisting of M-type supergiants that become later (cooler) with increasing luminosities. This separation is only partially reflected in the evolutionary tracks, although that might be due to the mis-match in metallicities between the solar Geneva models and the higher-than-solar metallicity of M31. As the luminosities increase the median spectral type also increases; i.e., the higher mass RSGs spend more time at cooler temperatures than do those of lower luminosities, a result which is new to this study. Finally we discuss what would be needed observationally to successfully build a luminosity function that could be used to constrain the mass-loss rates of RSGs as our Geneva colleagues have suggested.