Terrestrial exoplanets are observationally challenging to detect and characterize. Compared to gas giant exoplanets, terrestrial exoplanets introduce significantly smaller radial velocity signals and transit depths on their host stars. The signals are larger for terrestrial exoplanets orbiting M-dwarf stars, which have lower masses and radii than Sun-like F, G and K-type stars, and dominate stellar populations by number. Detecting exoplanets around M dwarfs is itself difficult because of their lower luminosities and lower flux at visible wavelengths, where most radial velocity and transit exoplanet surveys operate. I present here the motivation, development and results from a radial velocity program conducted on M dwarfs using near-infrared wavelengths, where M dwarf spectra peak in flux. To achieve high radial-velocity precision, I have used a technique called externally dispersed interferometry. It involves the combination of an interferometer and a moderate-resolution spectrograph on the 200 inch (5.1 m) Hale Telescope at Palomar Observatory. The TripleSpec Exoplanet Discovery Instrument, or TEDI, is the first such instrument to operate at near-infrared wavelengths. Our results indicate that contamination by narrow absorption lines introduced by the Earth's atmosphere limit radial velocity performance to that which can detect gas giant planets. I have conducted a survey of nearby M dwarfs, and can rule out with 3[sigma] confidence the presence of short-period gas giant planets in circular orbits around a few nearby M dwarfs. The results of this experiment direct future extrasolar planet instrumentation toward spectral regions with little telluric contamination and with higher resolution, to detect terrestrial exoplanets orbiting M dwarfs.