I think one can at least give a First Fundamental Theorem in the spirit of *really* classical invariant theory.
For the group $S_n$, I think you can build all invariants of vectors $(X_i)_{1\le i\le n}$ under the action by permutation matrices using tensor contractions with the following fundamental tensors $T^{(1)},\ldots,T^{(n)}$ given by:
$$
(T^{(k)})_{i_1,\ldots,i_k}=\prod_{1\le \alpha<\beta\le k} \delta_{i_{\alpha},i_{\beta}}\ .
$$
For instance, using Einstein's convention for summation over repeated indices,
$$
p_k=(T^{(k)})_{i_1,\ldots,i_k} X_{i_1}\ldots X_{i_k}
$$
give the power sums.
I think one can prove this following the very general recipe in this MO answer.

Now to go to a product $S_n\times S_n$ you can follow the procedure in this other MO answer.
Basically you need a duplicate collection of fundamental tensors, say $S^{(1)},\ldots,S^{(n)}$ given by the same formulas. Now if you have a product of $X_{ij}$ the rule is the $T$'s only contract to $i$-type row indices,
whereas the $S$'s only contract to the $j$-type column indices. Of course you need to contract everything in sight. This will give an infinite *linearly* generating set for the ring of invariants you are looking for indexed by bipartite graphs. The degree of an invariant is the number of edges. Now finding a finite subset of such graphs which will give a system of ring generators, that's the big problem I think Dima is referring to.

Some references which discuss the invariant theory for $S_n$ with the $T^{(k)}$ tensors are: