We present details of an approach to creating a k-distribution radiative transfer model (KDM) for use in the Martian atmosphere. Such models preserve the accuracy of more rigorous line-by-line models, but are orders of magnitude faster, and can be effectively implemented in 3-D general circulation models. The approach taken here is sufficiently generalized that it can be employed for atmospheres of any arbitrary composition and mass, and demonstrations are provided for simulated atmospheres with a present-day Martian surface pressure (6 mb) and a putative thick early Mars atmosphere (500 mb), both with and without atmospheric water vapor. KDM-derived absorption coefficients are placed into a look-up table at a set of gridded points in pressure, temperature and atmospheric composition, and a tri-linear interpolation scheme is used to obtain the coefficients appropriate for the local atmospheric conditions. These coefficients may then be used within any of a variety of commonly used flux solvers to obtain atmospheric heating rates. A series of validation tests are performed with the KDM for both present-day and early Mars atmospheric conditions, and the model is compared against several other widely used radiative transfer schemes, including several used in contemporary general circulation models. These validation results identify weaknesses in some other approaches and demonstrate the efficacy of the KDM, providing a rigorous test of these types of models for use in the Martian atmosphere. A demonstration of results obtained by implementing the KDM in a Mars general circulation model is provided.