Let $\text{Rank}{(A - \lambda I)^k} = \text{Rank}{(B - \lambda I)^k}$. Why are $A$ and $B$ similar? Let $A$ and $B \in M_n$ be two matrices such that $$\forall k=1,2,\dots,n,\ \forall \lambda\  \text{eigenvalue of $A$},\ \text{Rank}{(A - \lambda I)^k} = \text{Rank}{(B - \lambda I)^k}.$$ Why are $A$ and $B$ similar?
 A: Your question is quite unclear as to what field we consider. As darij grinberg remarked, this is false on a general field.
Example. Let $\theta$, $\phi \in \left]0,\pi\right[$ be two distinct angles. Then the rotation matrices
$$\begin{pmatrix} \cos \theta & -\sin \theta \\ \sin \theta & \cos \theta \end{pmatrix}\quad \text{and} \quad \begin{pmatrix} \cos \varphi & -\sin \varphi \\ \sin \varphi & \cos \varphi \end{pmatrix}$$
have no real eigenvalues. Still, these two matrices are not similar because their traces, $2 \cos \theta$ and $2 \cos \varphi$ are different.
A reasonable answer to your question is the following result.
Proposition. Let $K$ be an algebraically closed field. We denote by $\mathrm{Spec}(A)$ the set of eigenvalues of $A$ in $K$. Then, if
$$\forall \lambda \in \mathrm{Spec}(A),\ \forall 1 \leq k \leq n,\  \mathrm{rk}(A - \lambda I_n)^k = \mathrm{rk}(B - \lambda I_n)^k,$$
$A$ and $B$ are similar.
This proposition is a quite direct consequence of the following important result which explains the classification of matrices up to similarity in an algebraically closed field.
Theorem (Jordan normal form). Let $K$ be an algebraically closed field and $A \in M_n(K)$. Then, for every $\lambda \in \text{Spec}(A)$, there exists integers $m(\lambda)$ and $s_1(\lambda) \leq s_2(\lambda) \leq \cdots \leq s_{m(\lambda)}(\lambda)$ such that $A$ is similar to a block-diagonal matrix whose blocks are the $J_{s_i}(\lambda)$, for $\lambda \in \text{Spec}(A)$ and $i \leq m(\lambda)$, where
$$J_k(\lambda) = \begin{pmatrix} \lambda & 1 & 0 & \cdots & 0 \\ 0 & \lambda & 1 & \cdots & 0 \\ 0 & 0 & \lambda & \cdots & 0 \\ \vdots & \vdots & \vdots & \ddots & \vdots \\ 0 & 0 & 0 & \cdots & \lambda \end{pmatrix}.$$
Besides, there is unicity of this decomposition, in the sense that the $m(\lambda)$ and the $s_i(\lambda)$ are uniquely defined.
(In particular, note that $n$ is the sum of the $s_i$). I will need this remark later, so I'll call it the dimension formula.
I certainly won't prove this theorem. It is probably proved in any good linear algebra book, but I don't really know this kind of books in English ["the gods have imposed upon my writing the yoke of a foreign language that was not sung at my cradle"]. Jacobson's Basic Algebra I does it in its third chapter, but as a consequence of the classification of finitely generated modules over PIDs. It's very natural and enlightening, but it's not strictly necessary.
What I will do is deduce the proposition from the theorem.
Notations. I will use $m$ and the $s_i$ exactly as in the previous theorem. I will slightly extend it by considering that $m(\lambda) = 0$ if $\lambda$ isn't an eigenvalue of $A$. I will use $\mu$ and $\sigma_\iota$ for the corresponding attributes of $B$.
Because of the uniqueness part of the theorem, we have to prove that $\forall \lambda \in K, m(\lambda) = \mu(\lambda)$ and, for all $1 \leq i \leq m(\lambda)$, $s_i(\lambda) = \sigma_i(\lambda)$.
To prove the proposition, we have to prove that the different ranks you write are enough to determine the functions $m$ and $s_i$. To do that, remark that $\mathrm{rk}(J_s(\ell) - \lambda I_s)$ is $s$ if $\lambda \neq \ell$, but, if $k < s$,
$$\left(J_s(\ell) - \ell I_s\right)^k = J_s(0)^k$$
is a matrix having $s-k$ ones in the diagonal which is $k$ steps above the principal one. After that (for $k \geq s$), the matrix is $0$.
To sum up,
$$\left(J_s(\ell) - \ell I_s\right)^k = \begin{cases} s-k & \text{if } k \leq s \\ 0 & \text{if } k \geq s\end{cases} = (s-k)_+,$$
where the $+$ subscript means that, if the number in brackets is $< 0$, we replace it by $0$.
If you look at the decomposition, adding up the different blocks, you then get that $$\mathrm{rk}(A-\ell I_n)^k = \sum_{\lambda \neq \ell} m(\lambda) + \sum_{i=1}^{m(\ell)} (s_i(\ell) - k)_+.$$ 
In particular, note that, since all the $s_i(\ell)$ are $\leq n$, the quantities $\mathrm{rk}(A - \ell I_n)^k$ for $k > n$ (which are not included in the hypothesis of the proposition) are useless because they are simply $\sum_{\lambda \neq \ell} m(\lambda)=\mathrm{rk}(A - \ell I_n)^n.$
A small combinatorial reasoning then proves that your ranks determine everything: for $m$, this is direct:
$$\forall \lambda \in K,\ m(\lambda) = n - \mathrm{rk}(A - \lambda I_n)^n.$$
But it's a little more painful to write for the $s_i$. Basically, $\left(\mathrm{rk}(A - \lambda I_n)^k\right)_{k\geq 1}$ is a decreasing sequence and the "steps" are
$$\mathrm{rk}(A - \lambda I_n)^k - \mathrm{rk}(A - \lambda I_n)^{k+1} = \left| \left\{i \leq m(\lambda)\middle| s_i(\lambda) > k\right\}\right|.$$
And knowing how many $s_i(\lambda)$ are greater than $k$, for all $k$, is equivalent to knowing all of the $s_i(\lambda)$, because they are ordered. [Graphically, this is nothing but the transposition of Young tableaux, but I digress.]
At this stage, the proof is almost over. It would be over, but for the caveat that the hypothesis only gives the equalities between the ranks for $\lambda \in \mathrm{Spec}(A)$. The previous discussion then gives the equalities for all the $\lambda \in \mathrm{Spec}(A)$ and we still have to prove that $\forall \ell \in K \setminus \mathrm{Spec}(A), \mu(\ell) = 0$. This comes the fact that all the dimension has been "used up" to accomodate the blocks coming from $\textrm{Spec}(A)$.
More formally, it comes from the two dimension formulae for $A$ and $B$:
$$n = \sum_{\lambda\in K} \sum_{i=1}^{m(\lambda)} s_i(\lambda) = \sum_{\lambda \in \mathrm{Spec}(A)} \sum_{i=1}^{m(\lambda)} s_i(\lambda)$$
$$\begin{align*}
n &= \sum_{\lambda\in K} \sum_{i=1}^{\mu(\lambda)} \sigma_i(\lambda) \\
&= \sum_{\lambda \in \mathrm{Spec}(A)} \sum_{i=1}^{\mu(\lambda)} \sigma_i(\lambda) + \sum_{\lambda\not\in\mathrm{Spec}(A)}\sum_{i=1}^{\mu(\lambda)} \sigma_i(\lambda)\\
&= \sum_{\lambda \in \mathrm{Spec}(A)} \sum_{i=1}^{m(\lambda)} s_i(\lambda) + \sum_{\lambda\not\in\mathrm{Spec}(A)}\sum_{i=1}^{\mu(\lambda)} \sigma_i(\lambda)\\
&= n + \sum_{\lambda\not\in\mathrm{Spec}(A)}\sum_{i=1}^{\mu(\lambda)} \sigma_i(\lambda),\end{align*}$$
which gives $\sum_{\lambda\not\in\mathrm{Spec}(A)}\sum_{i=1}^{\mu(\lambda)}\sigma_i(\lambda) = 0$ so $\forall\lambda\not\in\mathrm{Spec}(A), \mu(\lambda) = 0$.
At last, we're done.
