You can use Jordan normal form, as Florian does, but you can also use rational canonical form, which gives a uniform theory over any field, and degenerates to Jordan normal form over an algebraically closed field. It is also a nice demonstration of the theory of modules over a PID at work. So, given a field $F$, and a non-zero monic polynomial $p(x) \in F[x],$ we want to classify $n \times n$ matrices $A$ such that $p(A) = 0,$ up to the usual similarity, ie up to conjugacy via an element of ${\rm GL}(n,F).$ These are (up to similarity), the matrices $A$ whose minimum polynomials $m_{A}(x)$ divide $p(x)$ in $F[x].$ There are clearly only finitely many possibilities for such minimum polynomials by uniqueness of factorization in $F[x],$ as minimum polynomials are monic. Hence it suffices to show that there are only finitely many similarity classes of matrices $A$ with a given minimum polynomial $m(x)$. We write the underlying space $V$ of (say) $n$-long column vectors as a direct sum of $A$-invariant subspaces $V = V_{1} \oplus V_{2} \oplus \ldots \oplus V_{k},$ where $k$ is the number of distinct irrducible factors of $m(x)$, and the minimum polynomial of $A$ on each $V_{i}$ is a power of the $i$-th irreducible factor. This reduces us to considering the case that $m(x)$ is a power of a single irreducible polynomial, say $m(x) = q(x)^{t}$ with $q(x)$ monic irreducible, and now $V = V_{1}.$ We may choose a vector $v \in V$ such that $q(A)^{t-1}v \neq 0,$ and then (with a little more theoretical justification , which I omit) ` $\{ v, Av,\ldots A^{dt-1}v \}$ is a basis for a direct summand $W$ of $V$ with respect to which the matrix of $A$ on $W$ is the uniquely determined so-called companion matrix of $m(x)$ (here, $d = {\rm deg}q(x) ).$ By the general theory again, there is an $A$-invariant complement $U$ of $W$ in $V$, and the minimum polynomial of $A$ on $U$ has the form $q(x)^{s}$ for some $s \leq t$. We continue inductively.