By using just the definition of a Cauchy Sequence, how could I show $s_n=n^2$ is not a Cauchy Sequence? Here's what I have,
Let $\epsilon>0$. Then there exists N such that $m,n>N \implies |n^2-m^2|<\epsilon.$
So now we have to find a $N$ that makes the implication true. So, $|n^2-m^2|<\epsilon=n^2<\epsilon+m^2=n<\sqrt{\epsilon+m^2}$. However, this can become arbitrarily large for large $m$. Hence, the sequence $s_n$ is not Cauchy.
I figure this can be written more formally, but I just want to know if what I typed is correct.

You have to show the sequence is not Cauchy. A sequence ${a_n}$is Cauchy if for every $\epsilon>0$ the statement: "There exists $N$ such that $n,m>N$ $\implies |a_n-a_m| < \epsilon$" is true.
So, to show the sequence is not Cauchy, we need to show that for atleast one particular number $\alpha$, the statement : "There exists $N$ such that $n,m>N$ $\implies |a_n-a_m| < \alpha$" is false. This means for that $\alpha$ :  "For all  $N$  there exist $n,m>N$ such that $|a_n-a_m| > \alpha$" is true. 
So, you have to make a choice of $\alpha$ and prove the statement : "For all  $N$  there exist $n,m>N$ such that $|a_n-a_m| > \alpha$"
