Red supergiants (RSGs) are evolved massive stars that represent extremes, in both their physical sizes and their cool temperatures, of the massive star population. Effective temperature ($T_{\rm eff}$) is the most critical physical property needed to place a RSG on the Hertzsprung-Russell Diagram, due to the stars' cool temperatures and resulting large bolometric corrections. Several recent papers have examined the potential utility of atomic line equivalent widths in cool supergiant spectra for determining $T_{\rm eff}$ and other physical properties (dorda2016b, dorda2016a) and found strong correlations between Ti I and Fe I spectral features and $T_{\rm eff}$ in earlier-type cool supergiants (G and early K) but poor correlations in M-type stars, a spectral subtype that makes up a significant fraction of RSGs. We have extended this work by measuring the equivalent widths of Ti, Fe, and Ca lines in late K- and M-type RSGs in the Milky Way, Large Magellanic Cloud, and Small Magellanic Cloud, and compared these results to the predictions of the MARCS stellar atmosphere models. Our analyses show a poor correlation between $T_{\rm eff}$ and the Fe I and Ti I lines in our observations (at odds with strong correlations predicted by stellar atmosphere models), but do find statistically significant correlations between $T_{\rm eff}$ and the Ca II triplet (CaT) features of Milky Way RSGs, suggesting that this could be a potential diagnostic tool for determining $T_{\rm eff}$ in M type supergiants. We also examine correlations between these spectral features and other physical properties of RSGs (including metallicity, surface gravity, and bolometric magnitude), and consider the underlying physics driving the evolution of atomic line spectra in RSGs.