Two-loop self-energy corrections to the bound-electron g factor are investigated theoretically to all orders in the nuclear binding strength parameter Zα. The separation of divergences is performed by dimensional regularization, and the contributing diagrams are regrouped into specific categories to yield finite results. We evaluate numerically the loop-after-loop terms, and the remaining diagrams by treating the Coulomb interaction in the electron propagators up to first order. The results show that such two-loop terms are mandatory to take into account for projected near-future stringent tests of quantum electrodynamics and for the determination of fundamental constants through the g factor.