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.