Treat $F^n$ as an $F[t]$-module $M^A$, where $t$ acts by the matrix $A$. Then the centralizer can be thought of as $\mathrm{End}_{F[t]} M^A$. Now, $M^A$ has a primary decomposition

$ M^A = \bigoplus_{p \in \mathrm{Irr}(F[t])} M_p$

where $M_p$ consists of vectors in $M^A$ which are annihilated by some power of $p(A)$. Likewise,

$C_{M_n(F)}(A)= \mathrm{End}_{F[t]} M^A = \bigoplus_p \mathrm{End}_{F[t]} M_p$

So the problem is reduced to the primary case, where the characteristic polynomial of $A$ is a power of some irreducible polynomial $p$.

Now, there exists a unique partition $\lambda=(\lambda_1,\dotsc,\lambda_l)$ such that

$M_p = \bigoplus_{i=1}^l F[t]/(p(t))^{\lambda_i}$.

As a vector space (and even as an $F[t]$-module), the endomorphism algebra of this module is the sum

$\bigoplus_{i,j} \mathrm{Hom}_{F[t]} (F[t]/(p(t))^{\lambda_i},F[t]/(p(t))^{\lambda_j})$.

The $(i,j)$th summand has dimension $(\deg p)\min\{\lambda_i,\lambda_j\}$. Therefore, the endomorphism algebra of this primary part is of dimension

$ (\deg p)\sum_{i,j} \min\{\lambda_i,\lambda_j\}$

To get the centralizer of the original matrix, you would add these numbers over all primary parts.
Finally, raising $q$ to this number is the cardinality that you want.

These centralizers are discussed in great detail in Pooja Singla's PhD thesis http://www.hbni.ac.in/phdthesis/allthesis/MATH10200604007_PSingla.pdf
and a related paper in J. Algebra 2010 (available on the arXiv at http://arxiv.org/abs/1001.5304v1).