Interactions of nanoscale structures with fluids are of current interest both in the elucidation of fluid dynamics at these small scales, and in determining the ultimate performance of nanoelectromechanical systems outside of vacuum. We present a comprehensive study of nanomechanical damping in three gases (He, N2, CO2), and liquid CO2. Resonant dynamics in multiple devices of varying size and frequency is measured over 10 decades of pressure (1 mPa-20 MPa) using time-domain stroboscopic optical interferometry. The wide pressure range allows full exploration of the regions of validity of Newtonian and non-Newtonian flow damping models. Observing free molecular flow behavior extending above 1 atm, we find a fluid relaxation time model to be valid throughout, but not beyond, the non-Newtonian regime, and a Newtonian flow vibrating spheres model to be valid in the viscous limit.