The Apache Point Observatory Galactic Evolution Experiment (APOGEE)—one of the Sloan Digital Sky Survey III programs—is using near-infrared (NIR) spectra of ~100,000 red giant branch star candidates to study the structure of the Milky Way. In the course of the survey, APOGEE also acquires spectra of hot field stars to serve as telluric calibrators for the primary science targets. We report the serendipitous discovery of two rare, fast-rotating B-stars of the σ Ori E type among those blue field stars observed during the first year of APOGEE operations. Both of the discovered stars display the spectroscopic signatures of rigidly rotating magnetospheres (RRM) common to this class of highly magnetized (B ~ 10 kGauss) stars, increasing the number of known RRM stars by ~10%. One (HD 345439) is a main-sequence B-star with unusually strong He absorption (similar to σ Ori E), while the other (HD 23478) fits a "He-normal" B3IV classification. We combine the APOGEE discovery spectra with other optical and NIR spectra of these two stars, and of σ Ori E itself, to show how NIR spectroscopy can be a uniquely powerful tool for discovering more of these rare objects, which may show little/no RRM signatures in their optical spectra. We discuss the potential for further discovery of σ Ori E type stars, as well as the implications of our discoveries for the population of these objects and insights into their origin and evolution.