We have performed a wide-area ultraviolet (UV) imaging survey using the GALaxy Evolution eXplorer (GALEX) to search for bright, point-like UV sources behind M31's extended halo. Our survey consisted of 46 pointings covering an effective area of ~50 deg^2, in both the far-UV and near-UV channels. We combined these data with optical R-band observations acquired with the WIYN Mosaic-1 imager on the Kitt Peak National Observatory 0.9m WIYN telescope. An analysis of the brightness and colors of sources matched between our photometric catalogs yielded ~100 UV-bright quasar candidates. We have obtained discovery spectra for 76 of these targets with the Kast spectrometer on the Lick 3m telescope and confirm 30 active galactic nuclei and quasars, 29 galaxies at z > 0.02 including several early-type systems, 16 Galactic stars (hot main-sequence stars), and one featureless source previously identified as a BL Lac object. Future UV spectroscopy of the brightest targets with the Cosmic Origins Spectrograph on the Hubble Space Telescope will enable a systematic search for diffuse gas in the extended halo of M31.