Is it true that given semi-simplicial sets $X,Y$, then $|X|×|Y|$ has a natural semi-simplicial structure?
I would guess that it is true, but I cannot find anything about it online. I know that the product in the category of semi-simplicial sets would not be a solution, since, for example, it occurs at every level on its own. And indeed, the realization functor does not preserve limits.
Yes. Let $X'$ and $Y'$ be the simplicial sets obtained from $X$ and $Y$ by adjoining degeneracies. Then $X'\times Y'$ is a simplicial set, which turns out to have the property that every face of a nondegenerate simplex is nondegenerate. So, if you let $Z$ consist of all the nondegenerate simplices of $X'\times Y'$, then $Z$ naturally has the structure of a semisimplicial set. We have canonical homeomorphisms $|Z|\cong |X'\times Y'|\cong |X'|\times |Y'|\cong |X|\times |Y|$, so this $Z$ is the semisimplicial set you seek.
Explicitly, a product of two simplices can be triangulated using simplices indexed by shuffles, as described at https://ncatlab.org/nlab/show/product+of+simplices. We apply this decomposition to each pair of simplices from $X$ and $Y$, and then glue them together to get $Z$.