I have proven that Martingales have orthogonal increments.
From this I need to show that $\operatorname{Cov}[M(t),M(s)]$ relies only on $\min\{s,t\}$.
I used the expected value definition of Covariance and eliminated one piece using the orthogonal increments bit. Also, I introduced conditioning on $F_s$.
$\operatorname{Cov}[M(t),M(s)]= E[(M(t)-E[M(s)])(M(s)-E[M(s)])]$
$= .... $
$= E[E[((M(t)+E[M(t)])E[M(s)]|F_s)]]$
From here I am lost.
Should I....
$ = E[E[M(t)E[M(s)]|F_s] +E[E[E[M(t)]*E[M(s)]|F_s]]$
$ = E[E[M(t)M(s)|F_S] + E[E[E[M^2(s)]|F_s]]$
I know $E[M(t)] = E[M(s)]$. Thats how I got the second piece of the second line.
Is this correct? Where should I go from there?
You are on the right track. Assuming $s<t$, by conditioning, $$ E[M(s)M(t)]=E[M(s)E[M(t)|\mathcal F_s]=E[M(s)^2]. $$ So, $$ cov[M(s),M(t)]=E[M(s)M(t)]-E[M(s)]E[M(t)]=E[M(s)^2]-(E[M(s)])^2=var[M(s)], $$ this depends on $t$ only through the fact that $t\in(s,\infty)$.