We investigate the combined effects of gravity, attractive interactions, and brownian motion in suspensions of colloidal particles and nonadsorbing polymer. Depending on the effective strength of gravitational forces, resulting from a density mismatch between the colloids and the solvent, and the magnitude and range of the depletion interactions induced by the polymer, sedimentation in these suspensions can result in an equilibrium structure or a kinetically arrested state. We employ large-scale molecular dynamics simulations to systematically classify the different regimes that arise as a function of attraction strength and gravitational stress. Whereas strong attractions lead to cluster aggregation and low-density arrested states, moderate attractions can enhance crystallization of the colloidal particles in the sediment. We make direct comparisons to experimental results to infer general conclusions about the mechanisms leading to mechanically stable sediments.