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.)