I have a statement $n \in N, \;n^2 \mod 3 = \{0, 1\}$, which basically says that any natural number $n$ when squared will have a remainder after dividing by $3$ of either $0$ or $1$.
From here I expended my proof into two cases
$n = 2k, n^2 = 4k^2$ and $n = 2k + 1, n^2 = 4k^2 +4k + 1$
From here I have a sense that $4 \mod 3 = 1$
and
$4 \mod 3 + 4 \mod 3 + 1 \mod 3 = 3 \mod 3 = 0$
But how do I prove this?
You're starting with the wrong idea. Write $n=3k$ or $n=3k+1$ or $n=3k+2$.
Working with residue classes modulo $3$ is of course the best strategy: if $[n]$ denotes the residue class of $n$, then $[n]=[0]$ or $[n]=[1]$ or $[n]=[2]$; since \begin{align} [0]^2&=[0],\\ [1]^2&=[1],\\ [2]^2&=[4]=[1], \end{align} the claim is proved.
This is not at all mysterious: Gauss's idea of using the residue classes is just formally forgetting the multiples of $3$ (or the modulo one uses) as computations go along.
You want to show that for $n\in \mathbb{N}$ either $3|n^{2}$ or $3|(n^{2}-1)$. By division with remainder, $n=3m+r$ where $0\leq r<3$ for some $m\in \mathbb{Z}$. Now you consider the three possible values of $r$.