We describe a method that exploits data from the Galaxy Evolution Explorer (GALEX) ultraviolet and Wide-field Infrared Survey Explorer and Two Micron All Sky Survey infrared source catalogs, combined with proper motions and empirical pre-main sequence isochrones, to identify candidate nearby, young, low-mass stars. Applying our method across the full GALEX-covered sky, we identify 2031 mostly M-type stars that, for an assumed age of 10 (100) Myr, all lie within similar to 150 (similar to 90) pc of Earth. The distribution of M spectral subclasses among these similar to 2000 candidate young stars peaks sharply in the range M3-M4; these subtypes constitute 50% of the sample, consistent with studies of the M star population in the immediate solar neighborhood. We focus on a subset of 58 of these candidate young M stars in the vicinity of the Tucana-Horologium association. Only 20 of these 58 candidates were detected in the ROSAT All-Sky X-ray Survey-reflecting the greater sensitivity of GALEX for the purposes of identifying active nearby, young stars, particularly for stars of type M4 and later. Based on statistical analysis of the kinematics and/or spectroscopic followup of these 58 M stars, we find that 50% (29 stars) indeed have properties consistent with Tuc-Hor membership, while 12 are potential new members of the Columba association, and 2 may be AB Dor moving group members. Hence, similar to 75% of our initial subsample of 58 candidates are likely members of young (age similar to 10-40 Myr) stellar moving groups within 100 pc, verifying that the stellar color-and kinematics-based selection algorithms described here can be used to efficiently isolate nearby, young, low-mass objects from among the field star population. Future studies will focus on characterizing additional subsamples selected from among this list of candidate nearby, young M stars.