Radial velocities measured from near-infrared (NIR) spectra are a potentially powerful tool to search for planets around cool stars and sub-stellar objects. However, no technique currently exists that yields NIR radial velocity precision comparable to that routinely obtained in the visible. We are carrying out an NIR radial velocity planet search program targeting a sample of the lowest-mass M dwarfs using the CRIRES instrument on the Very Large Telescope. In this first paper in a planned series about the project, we describe a method for measuring high-precision relative radial velocities of these stars from K-band spectra. The method makes use of a glass cell filled with ammonia gas to calibrate the spectrograph response similar to the "iodine cell" technique that has been used very successfully in the visible. Stellar spectra are obtained through the ammonia cell and modeled as the product of a Doppler-shifted template spectrum of the object and a spectrum of the cell, convolved with a variable instrumental profile (IP) model. A complicating factor is that a significant number of telluric absorption lines are present in the spectral regions containing useful stellar and ammonia lines. The telluric lines are modeled simultaneously as well using spectrum synthesis with a time-resolved model of the atmosphere over the observatory. The free parameters in the complete model are the wavelength scale of the spectrum, the IP, adjustments to the water and methane abundances in the atmospheric model, telluric spectrum Doppler shift, and stellar Doppler shift. Tests of the method based on the analysis of hundreds of spectra obtained for late-M dwarfs over 6 months demonstrate that precisions of ∼ 5 m s−1 are obtainable over long timescales, and precisions of better than 3 m s−1 can be obtained over timescales up to a week. The obtained precision is comparable to the predicted photon-limited errors, but primarily limited over long timescales by the imperfect modeling of the telluric lines.