Cosmic structure formation is characterized by the complex interplay between gravity, turbulence, and magnetic fields. The processes by which gravitational energy is converted into turbulent and magnetic energies, however, remain poorly understood. Here, we show with high-resolution, adaptive-mesh simulations that MHD turbulence is efficiently driven by extracting energy from the gravitational potential during the collapse of a dense gas cloud. Compressible motions generated during the contraction are converted into solenoidal, turbulent motions, leading to a natural energy ratio of E_sol/E_tot of approximately 2/3. We find that the energy injection scale of gravity-driven turbulence is close to the local Jeans scale. If small seeds of the magnetic field are present, they are amplified exponentially fast via the small-scale dynamo process. The magnetic field grows most efficiently on the smallest scales, for which the stretching, twisting, and folding of field lines, and the turbulent vortices are sufficiently resolved. We find that this scale corresponds to about 30 grid cells in the simulations. We thus suggest a new minimum resolution criterion of 30 cells per Jeans length in (magneto)hydrodynamical simulations of self-gravitating gas, in order to resolve turbulence on the Jeans scale, and to capture minimum dynamo amplification of the magnetic field. Due to numerical diffusion, however, any existing simulation today can at best provide lower limits on the physical growth rates. We conclude that a small, initial magnetic field can grow to dynamically important strength on time scales significantly shorter than the free-fall time of the cloud.