  We show that late Q-ball decay in the MSSM with gauge-mediated SUSY breaking
can provide a natural source of non-thermal NLSPs which subsequently decay to
gravitino dark matter without violating nucleosynthesis constraints. To show
this, we perform a global analysis of Q-ball formation and decay in
Affleck-Dine baryogenesis for a d = 6 (u^{c}d^{c}d^{c})^2 flat direction of the
gauge-mediated MSSM. A general phenomenological potential for the
flat-direction is studied and the Q-ball decay properties are obtained as a
function of its parameters. The corresponding gravitino mass necessary to
account for dark matter is then determined for the case of stau NLSPs. The
decay temperature depends on the charge of the Q-balls, which is determined by
the fragmentation of the AD condensate. Different fragmentation scenarios are
considered, and the final non-thermal NLSP density from Q-ball decay and NLSP
annihilation is determined. Particular care is taken to establish that NLSPs
from Q-ball decay become homogeneous and non-relativistic prior to
annihilation. The gravitino mass necessary for dark matter is naturally
consistent with the theoretical gravitino mass in the gauge-mediation model.
