If $\mathrm{rank}{(A - \lambda I)^k} = \mathrm{rank}{(B - \lambda I)^k}$ then $A$ is similar to $B$. 
Let $A,B \in M_n(\mathbb{C}).$ Suppose for all $\lambda  \in \mathbb C $ and for all $ k\in \mathbb Z_{+} $ we have $\mathrm{rank}(A - \lambda I)^k = \mathrm{rank}(B - \lambda I)^k.$ Then why are $A$ and $B $ similar? 

 A: Let $J^n_\lambda$ be a Jordan block of size $n\times n$ with $\lambda$ on the diagonal. Then $\mathrm{rank}(J^n_\lambda - \lambda I)^k=n-k$ for $k\leq n$ and otherwise it is zero. 
If we now take $A=J^n_\lambda \oplus J^m_\lambda $ with $m\leq n$, then you will get that $\mathrm{rank}(A - \lambda I)^k=m+n-2k$ for $k\leq m$ and for $m\leq k\leq n$ you will get that $\mathrm{rank}(A - \lambda I)^k=n-k$. 
In general, if $A$ is a sum of $d$ Jordan blocks (with eigenvalue $\lambda$), then 
$$\mathrm{rank}(A - \lambda I)^k-\mathrm{rank}(A - \lambda I)^{k+1}$$
is the number of block of size at least $k$, hence this numbers determines $A$.
Since $\mathrm{rank}(J^n_\lambda - \eta I)^k=n$ for $\eta \neq \lambda$, this can be generalized to arbitrary Jordan blocks. And finally, since the rank is invariant under conjugation, this is true for every matrix.
A: The Jordan theorem says that if $\sigma(A)=\sigma(B)$ and, for every $k$ and every $\lambda\in\sigma(A)$, $\mathrm{rank}((A-\lambda I)^k)=\mathrm{rank}((B-\lambda I)^k)$, then $A,B$ are similar.
It is equivalent to prove that the Jordan normal form of a given matrix is unique up to the order of the Jordan blocks. For an idea of the proof, read http://en.wikipedia.org/wiki/Jordan_normal_form
In fact, the complete proof is a long way. Read a book; it's your business! 
About your question, we must prove that $\sigma(A)=\sigma(B)$; the reason why is that the generalized eigenspaces of $A$ span whole $\mathbb{C}^n$ and, consequently, the generalized eigenspaces of $B$ associated to $\sigma(A)$ span also whole $\mathbb{C}^n$.
