Let $\tau$ denote the permutation matrix corresponding to $(1,2,\ldots,n)$. Consider it first as an element of $\mathrm{M}_n(q^2)$. 

This matrix has minimal polynomial equal to $X^n-1$, which is equal to its characteristic polynomial. It is therefore cyclic, and its centralizer is isomorphic to $\mathbb{F}_{q^2}$-algebra $\mathbb{F}_{q^2}[X]/(X^n-1)$. *For simplicity, I'll assume $\mathbb{F}_{q^2}$ has no $N$-th root of unity, so that this algebra is isomorphic to $\mathbb{F}_{q^{2n}}$.* Mapping $X\to \bar{X}^t$ defines a field automorphism of order $2$ of $\mathbb{F}_{q^{2n}}$ which, by Hilbert 90 (which is an overkill, but does the job), restricts to a surjective map $\mathbb{F}_{q^{2n}}^\times\to \mathbb{F}_{q^n}^\times$. The centralizer you're seeking is precisely the kernel of this map, and is of carinality
$$ \frac{q^{2n}-1}{q^n-1}=q^n+1.$$

Does this make sense?

Now, if $X^N-1$ splits in $\mathbb{F}_{q^2}$, then $\mathbb{F}_{q^2}[X]/(X^N-1)$ is a product of finite fields, and the same type of argument works per coordinate, which should result in a formula of the form $\prod_{i=1}^r q^{d_i}+1$ for suitable $d_i$'s such that $\sum d_i=n$.