We determine stellar parameters for the M dwarf GJ 436 that hosts a Neptune-mass planet. We employ primarily spectral modeling at low and high resolution, examining the agreement between model and observed optical spectra of five comparison stars of type, M0-M3. Modeling high resolution optical spectra suffers from uncertainties in TiO transitions, affecting the predicted strengths of both atomic and molecular lines in M dwarfs. The determination of Teff, gravity, and metallicity from optical spectra remains at ~10%. As molecules provide opacity both in lines and as an effective continuum, determing molecular transition parameters remains a challenge facing models such as the PHOENIX series, best verified with high resolution and spectrophotometric spectra. Our analysis of GJ 436 yields an effective temperature of Teff = 3350 +/- 300 K and a mass of 0.44 Msun. New Doppler measurements for GJ 436 with a precision of 3 m/s taken during 6 years improve the Keplerian model of the planet, giving a minimum mass, M sin i = 0.0713 Mjup = 22.6 Mearth, period, P = 2.6439 d, and e = 0.16 +/- 0.02. The noncircular orbit contrasts with the tidally circularized orbits of all close-in exoplanets, implying either ongoing pumping of eccentricity by a more distant companion, or a higher Q value for this low-mass planet. The velocities indeed reveal a long term trend, indicating a possible distant companion.