Let $M^2$ be a connected closed surface. Suppose there exists an embedding from a connected closed surface $N$ into the interior of $M \times [0,1]$ such that $N$ separates $M \times \{0\}$ and $M \times \{1\}$.
Can we prove the genus of $N$ is no smaller than that of $M$?
Nice question. Yes. Since you say "genus" I assume you implicitly mean to say oriented surfaces.
To be precise, if $i: N \to M \times [0,1]$ is the inclusion and $p: M \times [0,1] \to M$ is projection onto the first component, then $pi$ is degree 1.
To conclude, it is well-known that if $f: \Sigma_g \to \Sigma_h$ is a map of degree 1 then $g \geq h$. I leave it to you to provide or find a proof.
Proof of proposition. Write $M \times [0,1] = M_- \cup M_+$ with $M_- \cap M_+ = N$ and $M \times \{0\} \subset M_-$.
Write $i_0$ for the inclusions of $M \times \{0\}$ into $M \times [0,1]$.
Then (a suitable triangulation of) $M_-$ shows that $N$ and $M \times \{0\}$ are homologous in $M \times [0,1]$. That is, $$(i_0)_*[M] = i_* [N].$$
Composing with $p$ one finds that $$p_* (i_0)_* [M] = p_* i_* [N].$$ But $(p i_0) = 1_M$ and therefore $$p_* i_* [N] = [M],$$ and $pi$ is a degree 1 map as desired.