Can we characterize all integer matrices that are similar (over $\Bbb Z$) to a full Jordan block with $0$'a on the diagonal? In other words, can we determine the conjugacy class of such a matrix over $\Bbb Z$? The more general question is when we consider nonzero integers $b_1b_2\ldotsb_{n1}$ ($b_1$ divides $b_2$, $b_2$ divides $b_3$, etc.) on the upper diagonal, and $0$'s elsewhere.
One set of condition is that the matrix $A$ is nilpotent (which can be read off from the characteristic polynomial $p_A(t)$ being $t^n$) and that its cokernel is isomorphic to $\mathbb Z$ (or equivalently its elementary divisors are $n$ $1$'s and one $0$). Indeed considering (through $A$) $\mathbb Z^n$ as a module over $\mathbb Z[t]/(t^n)$ and letting $e\in\mathbb Z^n$ be a lift of a generator of $\mathbb Z^n/A\mathbb Z^n$ we get by Nakayama's lemma that it is a generator of $\mathbb Z^n$ as an $\mathbb Z[t]/(t^n)$module giving us a surjective $\mathbb Z[t]/(t^n)$modulemap $\mathbb Z[t]/(t^n)\rightarrow\mathbb Z^n$. It is also injective as that can be checked over $\mathbb Q$ in which case it is clear as $A$ as $\mathbb Q$matrix has a single Jordan block. As for the more general question a Jordan block of the assumed type has cokernel isomorphic to $\mathbb Z\bigoplus \mathbb Z/b_1\bigoplus\cdots\bigoplus\mathbb Z/b_{n1}$. I haven't really thought about it carefully but I doubt that that is the only invariant. 


An extended comment on Torsten's reasonable answer: It might be interesting to know why these special Jordan blocks are singled out at first. I guess these are (in oldfashioned language) Jordan forms of "nonderogatory" nilpotent matrices as treated in matrix algebra books (characteristic polynomial = minimal polynomial)? Anyway, there is quite a bit of older literature in this direction including a 1972 Academic Press book Integral Matrices by Morris Newman which integrates some group theory with linear algebra in the spirit of FrickeKlein. I'd approach the basic question here concretely by observing first that the matrices with rational entries similar to the given Jordan block are precisely the matrices over $\mathbb{Q}$ having this Jordan form. For this the point is to compare the rational canonical form over $\mathbb{Q}$ with the Jordan form over $\mathbb{C}$: here there is no problem with the eigenvalues of a given nilpotent matrix being in the smaller field. In turn, the similarity of an integral matrix with its Jordan form over $\mathbb{Q}$ using an invertible integral matrix runs into further problems of an arithmetic nature which I don't know how to analyze so concretely. In the broader Lietheoretic setting, you have the orbit of a regular nilpotent element in the full matrix algebra under the adjoint group associated to the general linear group. Here there are interesting arithmetic questions, when you start with an orbit over (say) $\mathbb{Q}$ and try to relate it to orbits under restriction to a natural arithmetic subgroup (here the group over $\mathbb{Z}$). There is substantial literature on all of this, related to features of a number field and its ring of integers, which I don't have at my fingertips. But that's probably the most natural setting for the question asked. The modern literature on arithmetic subgroups of reductive groups is extensive and beautiful. 


The answer to your first (less general) question is this : Let $A$ be a $n\times n$ matrix with coefficients in $\mathbb{Z}$. Then $A$ is similar over $\mathbb{Z}$ to a full Jordan block if and only if $Im(A^{n1})=Ker(A)$. (Here and afterwards, I am seeing $A$ as an endomorphism of $\mathbb{Z}^n$ and taking kernels and images there.) It is easy to see that this condition is necessary. To see that it is sufficient, you can go as follows : (1) Let $A$ be as before, but assume only that $A^n=0$. Then, for every $k\in\{1,\dots,n1\}$, the map $Ker(A^k)/(Im(A^{nk})+Ker(A))\longrightarrow Ker(A^{k1})/Im(A^{nk+1})$ induced by $A$ is injective. This is very easy. (2) Now assume that $Ker(A)=Im(A^{n1})$. From (1), we deduce that, for every $k\in\{1,\dots,n1\}$, $Ker(A^k)=Im(A^{nk})$. (3) Assume again that $Ker(A)=Im(A^{n1})$. Note that this implies that $A^n=0$ and $A^{n1}\not =0$, so that $Ker(A)$ is a $\mathbb{Z}$submodule of $\mathbb{Z}^n$ such that $Ker(A)\otimes_{\mathbb{Z}}\mathbb{Q}$ is $1$dimensional; from this we get that $Ker(A)$ is a free $\mathbb{Z}$module of rank $1$. Pick an element $e_n\in\mathbb{Z}^n$ such that $A^{n1}e_n$ is a generator of $Ker(A)$. For every $k\in\{1,\dots,n1\}$, let $e_k=A^{nk}e_n$. Then I say that $(e_1,\dots,e_n)$ is a basis of $\mathbb{Z}^n$. (And $A$ has the form we want in this basis, so we're done.) You can prove this last fact by induction on $n$. It is obvious for $n=1$. If $n>1$ and we know the fact for $n1$, then, by the induction hypothesis applied to the restriction of $A$ to $Im A=Ker(A^{n1})$ (seen as an endomorphism of this space), we get that $(e_1,\dots,e_{n1})$ is a basis of $Im(A)$. As $A(e_i)=e_{i1}$, this implies that $\mathbb{Z}^n=\mathbb{Z}e_2+\dots+\mathbb{Z}e_{n1}+Ker(f)$, but $Ker(f)=\mathbb{Z}e_1$, so we're done. Note that the following conditions are equivalent : (a) $Ker(A)=Im(A^{n1})$ (b) $Im(A)=Ker(A^{n1})$ (c) $A^n=0$ and $Coker(A)$ is isomorphic to $\mathbb{Z}$. So, in this particular case, the invariant given by Torsten Ekedahl is enough. In the general case, there are other invariants, and I don't know the general answer. For example, consider a $n\times n$ matrix $A$ with coefficients in $\mathbb{Z}$, and assume that it is similar (over $\mathbb{Z}$) to a matrix with $0$'s on the diagonal and under the diagonal, nonzero integers $b_1,\dots,b_{n1}$ on the upper diagonal (no divisibility condition) and some integers (zero or nonzero) elsewhere. Then the integers $b_1,\dots,b_{n1}$ are uniquely determined up to sign, because $b_1\dots b_k$ is the order of the quotient $Ker(A)/A^k(Ker(A^{k+1}))$. But these are still not the only invariants. For example, if $n=3$, we can see by direct calculation that the $GL_3(\mathbb{Z})$conjugacy classes of the matrices $$\left(\begin{matrix}0 & b_1 & c \\ 0 & 0 & b_2 \\ 0 & 0 & 0\end{matrix}\right)$$ and $$\left(\begin{matrix}0 & b_1 & d \\ 0 & 0 & b_2 \\ 0 & 0 & 0\end{matrix}\right)$$ (with $b_1,b_2$ positive integers) are the same if and only if $c=d$ modulo $gcd(b_1,b_2)$. For bigger $n$, it becomes more and more complicated, and I'm not sure what to do. (Perhaps some more experiments would indicate an answer ? A quick way to obtain necessary conditions is also to look at what happens for conjugacy over $\mathbb{Z}_p$; the problem becomes much simpler there, especially with your divisibility hypothesis, because there's only one prime in $\mathbb{Z}_p$. But I don't know if you can get sufficient conditions this way.) 

