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.  Since $M$ is orientable, any such surface is one-sided.  We now "compress".  

**Exercise 2.** Compressing a surface does not change the homology class represented (nor the number of sides).  (See the proof of Lemma 6.3 of "3-manifolds" by Hempel for a very similar technique.)
 
Thus we eventually arrive at the desired one-sided incompressible surface.