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.