Here is how Fermat probably did it (it is how I did it - not all of the steps were needed but I have to believe this was close to Fermat's thought process).

Any prime of the form $8n+1$ or $8n+3$ can be written in the form $a^2 +2b^2$. This is proved with descent techniques once realizes that $-2$ and $1$ are squares mod $8n+1$ or $8n+3$ and hence setting $a^2=-2$ and $b^2 = 1$ gets the result of $0$ (mod $8n+1$ or $8n+3$) for $a^2+2b^2$, which means our prime divides the result.
Any prime of the form $8n+5$ or $8n+7$ cannot be.

Point two is that combinations of squares with common shapes when multiplied by each other retain their shape. Let $x = a^2 + Sb^2$, and $y = c^2 + Sd^2$.
$xy = (ac+Sbd)^2 + S(ad-bc)^2 = (ac-Sbd)^2 + S(ad+bc)^2$

Point three is that if $y$ is even $y^2 + 2$ is even as is $x^3$. Dividing both sides by $2$ would make the left hand side odd and right hand side even so both $y$ and $x$ are odd.

Point four is that if a non-prime is of the form $a^2 + 2b^2$ then all its prime factors must be of the form $8n+1$ or $8n+3$, or the factor must be a square.

Point five is to observe that $y^2 + 2$ is of the form $a^2 + 2b^2$ with $a=y$ and $b=1$. Combining this with four and one means there are no squares of the form $8n+5$ or $8n+7$ since $b$ would be equal to that square, not $1$.

So now we expand upon point three to make the proof. $x$ is of the form $a^2 + 2b^2$. $x^3$ can be written as $(a^3-3Sab^2)^2 + S(3a^2b-Sb^3)^2$. Letting $S=2$ we see that the expression $(3a^2b-2b^3)^2$ must be equal to $1$. Hence $b^2 \cdot (3a^2-2b^2)^2 =1$. Using positive integers we see $b=a=1$ is the only solution. Hence $x =1^2 + 2*1^2 = 3$ is the only possibility and $5^2 + 2 =3^3$ is the only solution