Source for roots of matrix polynomials? A
matrix polynomial
is a polynomial whose variables are square $n \times n$ matrices,
let's say with entries in $\mathbb{C}$, and with coefficients in $\mathbb{C}$.
I am seeking a source of results on solving such equations.
For example, $X^2 =0$ has infinitely many solutions, because, e.g.,
$$ X =
\left( \begin{array}{ccc}
0 & 0 & x \\
0 & 0 & 0 \\
0 & 0 & 0 \end{array} \right)
$$
is a solution for all $x \in \mathbb{C}$.
(Second example removed, as it did not fit the definition.)
There is such a rich set of results on roots of polynomial equations over $\mathbb{C}$
and over $\mathbb{R}$, I am hoping there are analogs when the variables are matrices
rather than single elements of fields. But my (superficial) explorations did
not uncover a comprehensive source on this topic.
To pose a specific question:

Q. Are there theorems that yield the number of solutions/roots
  for such matrix polynomial equations?

 A: As Geoff Robinson says, a Jordan form takes you quite far. Evaluating a scalar polynomial (or an analytic function) $f(x)$ at a Jordan block $J_{\lambda,t}$ of size $t$ and eigenvalue $\lambda$ gives the triangular Toeplitz matrix
$$
f(J_{\lambda,t})=
\begin{bmatrix}
f(\lambda) & f'(\lambda) & f''(\lambda) & \dots & f^{t-1}(\lambda)\\
0 & f(\lambda) & f'(\lambda) & \ddots & \vdots\\
0 & 0 & \ddots & \ddots & \vdots \\
\vdots & \vdots & \ddots & \ddots & \vdots\\
0 & 0 & \dots & 0 & f(\lambda)
\end{bmatrix}.
$$
So evaluating $f(A)$ where $A$ has Jordan form $A=M (\bigoplus J_{\lambda_i,t_i}) M^{-1}$ gives $M(\bigoplus f(J_{\lambda_i,t_i}))M^{-1}$.
In other words, for $f(A)$ to be zero, $f$ needs to satisfy $f(\lambda)=0,f'(\lambda)=0,f''(\lambda)=0,\dots,f^{(t-1)}(\lambda)=0$, for each eigenvalue $\lambda$ of $A$ with algebraic multiplicity $t$. Conversely, given $f$, the matrices at which it vanishes are all those who have eigenvalues equal to the scalar roots of the polynomial, with algebraic multiplicities smaller or equal than their multiplicities as scalar roots of $f$. This is just a complicated way to state that $f$ has to be a multiple of the minimal polynomial of $A$ (which sounds quite obvious).
This solves completely your first example; as for the second, it doesn't quite fit your definition, as has been pointed out in the comments.
A reference for the computation of $f(J_{\lambda,t})$, and other equivalent definitions of functions evaluated at a matrix argument, is Chapter 1 of Higham, Functions of matrices.
A: (Covers question as originally asked)
Well, in the cases you cite, Jordan normal form already takes you quite far. If you want to solve $p(X) = M $ for $n \times n$ complex matrices $X$ and $M$ and $p(t) \in \mathbb{C}[t],$ then if there is a solution at all, the matrix $X$ must act on each generalized eigenspace of $M,$ as it certainly should commute with $M.$ Hence over an algebraically closed field, you may as well reduce to the case that $M$ has a single eigenvalue. Over a field which is not necessarily algebraically closed, you can reduce via rational canonical form to the case that $M$ has a characteristic polynomial which is a power of a singe irreducible polynomial. But it isn't clear to me what generality you want to work in.
Later edit: (Complex case): Solving $p(X) = M$ when $M$ has a single eigenvalue reduces easily to the case when $M$ is nilpotent ( with $p(t)$ replaced by $q(t) - \lambda$ for some scalar $\lambda$). This in turn reduces to piecing together in a consistent fashion solutions to equations $Y^{d} = N^{\prime},$ where both $Y$ and $N^{\prime}$ are nilpotent, and $Y$ has a single Jordan block ( if there is a solution,$M$ must respect any decomposition of the space into indecomposable $X$-invariant summands,and we consider each such indecomposable summand separately). Then it is a question of determining the Jordan normal form of $Y^{d}$ when $Y$ is a nilpotent matrix with a single Jordan block.
Note that if $M$ is diagonalizable, there is always a complex solution, and that, in that case,  there are finitely many solutions if $M$ has no repeated eigenvalue.
A: Well, the Riccati matrix equation and its variants transform (assuming the leading "coefficient" is invertible) to the quadratic $Z^2 + AZ + B = 0$ (where $Z$ is the unknown matrix and $A,B$ are square). There are generically $C(2n,n)$ solutions, although there could be less, or a continuum (but not greater than $C(2n,n)$ and less than $c$); if $A$ and $B$ commute, the generic number is $2^n$. 
One reference is,
D Handelman [me], Fixed points of two-sided fractional matrix transformations, Fixed point theory and its applications, 2007, ID41930, doi:10.1155/2007/41930, 
which is freely downloadable.
It's mainly concerned with fixed points of the densely-defined transformation (on $n \times n$ matrices) $X \mapsto (I - CXD)^{-1}$ (where $C$ and $D$ are given), which can be transformed into the quadratic above, and variations on it. It turns out there is a natural graph structure on the solutions, which is generically the Johnson graph.
Edit: Oops, on rereading your question, I see that you required the coefficients to be scalars, which is much more tractible. Oh well, never mind. (If you remember Gilda Radner on SNL ....)
A: Although your question is formulated over $\mathbb{C}$, I still think it is interesting to point out how number theory comes up when you study this problem over rings, not fields. I will discuss the special situation of the equation $f(M)=0$ with $f$ a separable polynomial (irreducible most of the time).
First, let me rephrase the answers given by Geoff Robinson and Federico Poloni: if $k$ is a field and  $f$ is a separable polynomial of degree $n$ over $k$, then the equation $f(M)=0$ has - up to conjugacy with matrices from $GL_n(k)$ - a single solution in $M_n(k)$. One particular solution is the companion matrix of $f$, and all the others are obtained by conjugation. 
Now if we are trying to solve $f(M)$ in $M_n(\mathbb{Z})$, the type of answer changes. There is a classical theorem of Latimer and MacDuffee (C.G. Latimer and C.C. MacDuffee. A correspondence between classes of ideals and classes of matrices. Ann. of Math. (2) 34 (1933), no. 2, 313-316) that sets up a bijective correspondence between conjugacy classes of matrices with characteristic polynomial $f$ and ideal classes in the extension $\mathbb{Z}[\alpha]$, where $\alpha$ is a root of $f$. You can get from ideal classes to matrices by picking a basis of a representing ideal and writing down the representing matrices of multiplication with $\alpha$. A more modern writeup of this correspondence can be found in these notes of Keith Conrad. Using this correspondence, you get finiteness of the number of conjugacy classes from the finiteness of the ideal class group, a basic theorem in algebraic number theory. As a simple application, there are $3$ conjugacy classes of elements of order $23$ in $GL_{22}(\mathbb{Z})$, which may not be obvious without the algebraic number theory background. 
This correspondence can be generalized beyond the case of $\mathbb{Z}$, but requires more number theory then. 
A: A comment on the simplest case of the revised question: Given $\alpha,\beta \in \mathbb{C}$ consider $f(x)=x^2+\alpha x+\beta.$  The solutions in $2 \times 2$ complex matrices $X$ of $f(X)=X^2+\alpha X+\beta I$ are as follows:


*

*either $1$ or $4$ solutions in diagonal matrices (according as $f$ has $1$ or $2$ distinct complex roots)

*A two parameter family of non-diagonal solutions.
A diagonal solution must be $X =
\left( \begin{array}{cc}
a &0 \\
0 & d \end{array} \right)$ with $f(a)=f(d)=0$
A solution $X =
\left( \begin{array}{cc}
a &b\\
c & d \end{array} \right)$ with $b,c$ not both $0$ must have 


*

*$a+d=-\alpha$ and 

*$bc=-(a^2+\alpha a +\beta)$ and 

*$bc=-(d^2+\alpha d+\beta).$ 


However the first two equation makes the second two equivalent since $a^2+\alpha a=-ad=d^2+\alpha d.$
So the diagonal entries (for this non-diagonal case) come from a line in the $a,d$ plane and this choice forces the off diagonal entries to come from a hyperbola in the $b,c$ plane (which may be the degenerate case $bc=0$ of two perpendicular lines.)
A: F.R. Gantmaher, The theory of matrices is a good reference of this subject, in my opinion.
A: The following sentence by Federico
"Conversely, given f, the matrices at which it vanishes are all those who have eigenvalues equal to the scalar roots of the polynomial, with algebraic multiplicities smaller or equal than their multiplicities as scalar roots of f"
seems to me unclear.  
We want to solve the equation (E): $p(X)=0$ - where $p\in K[x]$ - in the unknown $X\in M_n(K)$. 
i) $K$ is an algebraic closed field. The roots of $p$ are $(\alpha_i)_{i\leq s}$ with multiplicity $(r_i)_{i\leq s}$. Let $J_r$ be the nilpotent Jordan block of dimension $r$. Then $X$ is a solution of (E) IFF $X$ is similar to  $diag(U_1,\cdots,U_k)$ for any choice of $k$ and of the dimension $n_j$ of $U_j$ satisfying $n_1+\cdots+n_k=n$ and for any choice of $U_j$ among the matrices of following forms: $\alpha_i I_{n_j}+J_{n_j}$ with $i\leq s$ and $n_j\leq r_i$.
ii) $K$ is a field not alg. closed. We factor $p$ in irreducible $p=p_1^{r_1}\cdots p_s^{r_s}$. The result is similar to that of i). It suffices to choose $U_j$ among the companion matrices of ${p_i}^{q}$ where $q=n_j/degree(p_i)$ and $q\leq r_i$.
iii) $K$ is an euclidean ring (for example $\mathbb{Z}$). As Matthias wrote, it is much more difficult. We must seek a number of ideal classes ; using Magma software, we can do that but, morover, we must find one representant in each class, that is not obvious. For example, solve $A^3=I_n$ where $A\in M_n(\mathbb{Z})$. 
Note that, obviously, this Joseph's question has not research level. Yet everyone rushes to give its answer (me also !). Hilarious detail: "il maestro" Joseph has $43800$ points. Compare with this post sent on MO and on MSE by an unknown user - here $K=\mathbb{Z}[i]$ -
https://math.stackexchange.com/questions/634655/how-to-find-all-the-solutions-to-ia-cdotsan-0
this question (in my opinion) is difficult and interesting. Yet the post was expelled from MO because it had not the research level. Hilarious detail: this poor unknown user has only $91$ points. La Fontaine, a great French poet (not the same as the poet of Michael Connelly), wrote (in french) "Selon que vous serez puissant ou misérable,
Les jugements de cour vous rendront blanc ou noir", that is (in my bad non idiomatic English) "Depending on whether you will be powerful or miserable,
Court judgments make you white or black".
