I seem to recall that the answer is $p + 1$, but I'm not quite sure.

$\begingroup$ See mathoverflow.net/q/84897/297 $\endgroup$ – David E Speyer Jul 12 at 20:24
Depends on what you mean by "quaternions" and "distinct". If you mean quaternions $a + b{\bf i} + c{\bf j} + d{\bf k}$, with $a,b,c,d$ all integers, then you're asking to count solutions of $a^2+b^2+c^2+d^2 = p$, which by Jacobi's four squares theorem is $8$ times the sum of positive divisors of $p$, i.e. $8(p+1)$. If you then identify quaternions ${\bf q}$ with ${\bf qu}$ or ${\bf uq}$ (but not both!) where $\bf u$ is one of the eight units $\pm 1, \pm{\bf i}, \pm{\bf j}, \pm{\bf k}$, then there are $p+1$ distinct solutions as desired.