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.