Regarding Similarity of matrices Consider a set $T$ of square matrices over finite field $\mathbb{F_p}$. Clearly the cardinality of the set $T$ is $p^{n^2}$ where the square matrices are of size $n$. 
Question is: How many non-similar ($A=P^{-1}.B.P$ for some $P$ $\in$ $T$) matrices we would have? 
Next, suppose there are two matrices $A$ and $B$ such that their minimal polynomial is same $f$ (say). Question is: Are $A$ and $B$ similar matrices?

To your second question: no, the minimal polynomial does not suffice. As an example, consider the following two matrices
$$
A = \begin{bmatrix}
0 & 1 & 0 & 0\\
0 & 0 & 0 & 0\\
0 & 0 & 0 & 0\\
0 & 0 & 0 & 0\\
\end{bmatrix},
\qquad
B = \begin{bmatrix}
0 & 1 & 0 & 0\\
0 & 0 & 0 & 0\\
0 & 0 & 0 & 1\\
0 & 0 & 0 & 0\\
\end{bmatrix}.
$$
They have the same minimal polynomial, namely $x^{2}$, but they are not similar. Similarity depends in general not on a single polynomial, but on a sequence of polynomials, each dividing the next one. For $A$ the sequence is $x, x, x^{2}$, for $B$ it is $x^{2}, x^{2}$.
A good reference is Jacobson's Basic Algebra I.

As to your first question, I refer you to this question and the answer provided there.
