Despite being one of the most well studied model organisms in biology, little is known about the locomotion of C. elegans in naturalistic settings. Ecological literature suggests that these animals contend with heterogenous environments like rotten fruit, soil and even the backs of insects; in contrast, the majority of behavioral studies of C. elegans are conducted in homogeneous Newtonian fluids or on the surface of agarose gels, where worms typically crawl forward via regular, undulating waves of body curvature. Using 3D, stereo-microscopy techniques, we image C. elegans burrowing in gel environments with tunable viscosities and bulk moduli, models of conditions in rotting fruit. Previous studies in fluids find that body undulation wavelengths and frequencies decrease with increasing resistance (increasing viscosity). In highly resistive non-Newtonian environments imposed by gels, this trend persists, however the motion displays complex, irregular undulatory patterns. Furthermore, kinematic differences in surface crawling and burrowing resemble those of the desert dwelling Shovel nosed snake (C. occipitalis) atop or within dry granular media. In both organisms, principal component analysis reveals a behavior well-captured by a small number of quasi-sinusoidal components, however the amplitude variation of these components in the burrowing case displays a much higher degree of complexity, accounting for the qualitative differences in body shape. We conjecture that burrowing introduces a distinct neuromechanical regime, likely arising from physiological constraints on power or force production by the muscles. Finally, our experiments reveal new complex turning behaviors featuring dramatic body bends and multiple self-intersections seldom observed in other conditions.