We present the first results from our planet-search program using the 9.2 m Hobby-Eberly Telescope (HET) at McDonald Observatory to detect planets around M-type dwarf stars by means of high-precision radial velocity (RV) measurements. Although more than 100 extrasolar planets have been found around solar-type stars of spectral type F-K, there is only a single M dwarf (GJ 876) known to harbor a planetary system. With the current incompleteness of Doppler surveys with respect to M dwarfs, it is not yet possible to decide whether this is due to a fundamental difference in the formation history and overall frequency of planetary systems in the low-mass regime of the Hertzsprung-Russell diagram, or simply an observational bias. Our HET M dwarf survey plans to survey 100 M dwarfs in the next 3 to 4 years, with the primary goal being to answer this question. Here we present the results from the first year of the survey, which show that our routine RV precision for M dwarfs is 6 m s(-1). We found that GJ 864 and GJ 913 are binary systems with as yet undetermined periods, while five out of 39 M dwarfs reveal a high RV scatter and represent candidates for having short-period planetary companions. For one of them, GJ 436 (rms = 20.6 m s(-1)), we have already obtained follow-up observations, but no periodic signal is present in the RV data.