Could anyone give me any hints as to how to prove this?
I've tried using Euler's formula $3^\frac{p-1}{2} \equiv \left(\frac{3}{p}\right)\bmod p$, and quadratic reciprocity but I'm not getting anywhere!
I've tried messing around with the Legendre symbol, and I've looked at the proofs which show for what primes $p$, $-1$ and $2$ are quadratic residues, but I'm stuck on this one!
You're close: $\left(\frac{3}{p}\right)=\left(\frac{p}{3}\right)(-1)^{\frac{p-1}{2}}$ by reciprocity. So, either $\left(\frac{p}{3}\right)=1$ and $p=1 \bmod{4}$ or $\left(\frac{p}{3}\right)=-1$ and $p=3 \bmod{4}$. Can you finish it off yourself from here?