A new generalized nonlinear Schrödinger equation describing the propagation of ultrashort pulses in bulk media exhibiting frequency dependent dielectric susceptibility and magnetic permeability is derived and used to characterize wave propagation in a negative index material. The equation has new features that are distinct from ordinary materials (mu=1): the linear and nonlinear coefficients can be tailored through the linear properties of the medium to attain any combination of signs unachievable in ordinary matter, with significant potential to realize a wide class of solitary waves.