It depends on the Jordan canonical form of $A$. For example, suppose
$$
A = \pmatrix{\lambda & 1 & 0 & 0 & 0\cr 0 & \lambda & 1 & 0 & 0\cr
0 & 0 & \lambda & 0 & 0\cr
0 & 0 & 0 & \lambda & 1\cr
0 & 0 & 0 & 0 & \lambda\cr}$$
Then in order to commute with $A$, $B$ must be of the form
$$ \left...
The relevant part is:
> In general, suppose $A$ has $m$ Jordan blocks of sizes $s_i$, $i= 1.. m$, and let $e(i,j) = 1$ if blocks $i$ and $j$ have the same eigenvalue, $0$ otherwise. Then the dimension is $$\sum_{i=1}^m \sum_{j=1}^m e(i,j) \min(s_i,s_j)$$