We present a method for isolating a clean sample of red giant stars in the outerregions of the Andromeda spiral galaxy (M31) from an ongoing spectroscopic survey using the DEIMOS instrument on the Keck 10-m telescope. The survey aims to study the kinematics, global structure, substructure, and metallicity of M31's halo. Although most of our spectroscopic targets were photometrically screened to reject foreground Milky Way dwarf star contaminants, the latter class of objects still constitutes a substantial fraction of the observed spectra in the sparse outer halo. Our likelihood-based method for isolating M31 red giants uses five criteria: (1) radial velocity, (2) photometry in the intermediate-width DDO51 band to measure the strength of the MgH/Mgb absorption features, (3) strength of the Na I 8190A absorption line doublet, (4) location within an (I, V-I) color-magnitude diagram, and (5) comparison of photometric (CMD-based) versus spectroscopic (Ca II 8500A triplet-based) metallicity estimates. We also discuss K I and TiO diagnostics for giant/dwarf separation that might be useful in future analyses. Training sets consisting of definite M31 red giants and Galactic dwarf stars are used to derive empirical probabilitydistribution functions for each diagnostic. These functions are used to calculate the likelihood that a given star is a red giant in M31 versus a Milky Way dwarf. By applying this diagnostic method to our spectroscopic data set, we isolate 40 M31 red giants beyond a projected distance of R = 60 kpc from the galaxy's center, including three out at R ~ 165 kpc. The ability to identify individual M31 red giants gives us an unprecedented level of sensitivity in studying the properties of the galaxy's outer halo.