There is a fruitful way of thinking about the algebra $\mathbb{C}[M_{n,m}]^{{O_n}\times O_m}$ that originates from the $(GL_n, GL_m)$-duality. Namely,
$$
\mathbb{C}[M_{n,m}]=\bigoplus_{\lambda}V_n^{\lambda}\otimes V_m^{\lambda},
$$
where the sum is over all partitions $\lambda$ with at most $\min(n,m)$ parts and $V_n^\lambda$ is the polynomial representation of $GL_n$ with highest weight $\lambda=(\lambda_1,\lambda_2,\ldots)$ with zeros appended at the end to make it length $n,$ and similarly for $m.$ Now, since $O_n$ is a spherical subgroup of $GL_n$, the space of $O_n$-invariants $V_n^{\lambda}$ is at most one-dimensional; it is non-zero precisely when $\lambda$ is even (i.e. all parts are even). A good source for these results is Roger Howe's Schur Lectures.
It follows that as a vector space,
$$
\mathbb{C}[M_{n,m}]^{O_n\times O_m}=\bigoplus_{\lambda}(V_n^{\lambda})^{O_n}\otimes (V_m^{\lambda})^{O_m},
$$
and now the sum is over even partitions with the same restriction as before, and every summand is one-dimensional and is spanned by an explicitly described polynomial on $M_{n,m}$. Using standard techniques (described in the Schur lectures), this description can be amplified to yield the algebra structure as well. Namely, the algebra is graded by an affine semigroup of rank $\min(n,m)$ and is freely generated by explicit elements in degrees $2k$ for $1\leq k\leq \min(n,m).$ With a bit of extra work, one can also handle the more general case of $SO_n\times SO_m$ invariants.
Let me connect this description of the invariants with Abdelmalek's description following the path that Neil originally had in mind. Assume for concreteness that $n\geq m.$ The First Fundamental Theorem for $O_n$ in geometric form states that the map
$$
q:M_{n,m}\to Sym_{m,m} \qquad X\mapsto X^{T}X
$$
is the geometric quotient, i.e. it is $O_n$-invariant and gives rise to the isomorphism
$$
\mathbb{C}[M_{n,m}]^{O_n}\simeq \mathbb{C}[Sym_{m,m}].
$$
(The restriction $n\geq m$ assures that the image of $q$, which consists of symmetric matrices of rank at most $\min(n,m),$ is all of $Sym_{m,m}.$)
It is also clearly $GL_m$-equivariant, where $GL_m$ acts on the symmetric matrices of order $m$ by
$$
Y\to g^T Y g\qquad Y\in Sym_{m,m}, g\in GL_m,
$$
and, a fortiori, $O_m$-invariant. Now pass to the $O_m$-invariants! Under this identification,
$$
\mathbb{C}[M_{n,m}]^{O_n\times O_m} \simeq \mathbb{C}[Sym_{m,m}]^{O_m}.
$$
Thus the problem is reduced to determination of the orthogonal invariants of a symmetric matrix $Y$. It is well known that this invariant ring is freely generated by the coefficients of the characteristic polynomial of $Y.$ The coefficient of $\lambda^{m-k}$ has degree $k$ in the entries of $Y$ and, up to a sign, it is equal to the sum of the principal minors of $Y=X^T X$ of order $k, 1\leq k\leq m.$ Thus the fundamental invariants have degrees $2k, 1\leq k\leq m,$ in the entries of $X.$ Additionally, it can be verified that the $k$th fundamental invariant corresponds to the summand with $\lambda=(1^k)$ in the direct decomposition of $\mathbb{C}[M_{n,m}]^{O_n\times O_m}$ coming from the $(GL_n,GL_m)$-duality (i.e. the second highlighted decomposition above).