We present new measurements of differential cross sections for Z/gamma*(->mumu)+jet+X production in a 1 fb-1 data sample collected with the D0 detector in proton anti-proton collisions at sqrt{s}=1.96 TeV. Results include the first measurements differential in the Z/gamma* transverse momentum and rapidity, as well as new measurements differential in the leading jet transverse momentum and rapidity. Next-to-leading order perturbative QCD predictions are compared to the measurements, and reasonable agreement is observed, except in the region of low Z/gamma* transverse momentum. Predictions from two event generators based on matrix elements and parton showers, and one pure parton shower event generator are also compared to the measurements. These show significant overall normalization differences to the data and have varied success in describing the shape of the distributions.