Covariance of Martingales

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)$.
What is the mathematical meaning of 'rely on'? Typically, to compute covariances of martingales you can do the following. Suppose $s<t$ \begin{align} \mbox{Cov}[M(t),M(s)] &= \mbox{Cov}[M(t)-M(s)+M(s),M(s)] \\ &=\mbox{Cov}[M(t)-M(s),M(s)] + \mbox{Var}[M(s)] \\ &= \mathbb{E}[M(s)(M(t)-M(s))] - \mathbb{E}[M(t)-M(s)]\mathbb{E}[M(s)] + \mbox{Var}[M(s)] \\ \end{align} Using the orthogonal increment property we have that $\mathbb{E}[M(s)(M(t)-M(s))] = 0$ and hence for $s<t$ $$\mbox{Cov}[M(t),M(s)] = \mbox{Var}[M(s)].$$ The proof goes similar for $t<s$.