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).