Geoff already gave a description. Here is a semigroup theory approach. $M^{k+1}=M$ means that $E=M^k$ is an idempotent, $E^2=E$, and $EM=M=ME$. All idempotents in the matrix semigroup over $Z$ are easily described as matrices similar to diag$(0,...,0,1,1,...,1)$ (several 0's followed by several $1$'s) with unimodular conjugator. Hence we can assume that $E$ has that form. Therefore $M=EM=ME$ must have the form described in Geoff's answer. The same description holds for matrices over any ring if the structure of idempotents is similar to the above.

** Edit. ** As Geoff pointed out below, in fact since $EM=ME=M$, we get that the block $A$ in $M$ is 0, so $M$ looks like $$\left(\begin{array}{ll} 0&0\\\ 0 & B\end{array}\right)$$ where $B$ is an integer matrix with $B^k=1$. This is of course an "if and only if" description. I am pretty sure this has been known since the 50s, but I do not have time to dig it up. It should follow from the description of Green relations in the matrix semigroups.