This follows from two exercises.
Exercise 1. Every class in $H_2(M, \mathbb{Z}_2)$ is represented by a smooth embedded surface. (See Exercise 4.5.12(b) in "4-Manifolds and Kirby Calculus" by Gompf and Stipsicz.)
Suppose that the surface is $S \subset M$. If $S$ is orientable, then it bounds modulo $\mathbb{Z}$ and thus modulo $\mathbb{Z}_2$, a contradiction. Thus $S$ is not orientable. Thus $S$ has odd Euler characteristic. Since $M$ is orientable, any such surface (with odd Euler characteristic) is one-sided.
Exercise 2. If $M$ contains a surface of odd Euler characteristic, then any such with maximal Euler characteristic is incompressible. (See Lemma 6.3 of "3-manifolds" by Hempel.)