Interactions between micro-swimmers and their complex flow environments are important in many biological systems, such as sperm cells swimming in cervical mucus or bacteria in biofilm initiation areas. We present a theoretical model describing the dynamics of micro-organisms swimming in a plane Poiseuille flow of a viscoelastic fluid, accounting for hydrodynamic interactions and biological noise. General non-Newtonian effects are investigated, including shear-thinning and normal stress differences that lead to migration of the organisms across the streamlines of the background flow. We show that micro-swimmers are driven towards the centre-line of the channel, even if countered by hydrodynamic interactions with the channel walls that typically lead to boundary accumulation. Furthermore, we demonstrate that the normal stress differences reorient the swimmers at the centre-line in the direction against the flow so that they swim upstream. This suggests a natural sorting mechanism to select swimmers with a given swimming speed larger than the tunable Poiseuille flow velocity. This framework is then extended to study trapping and colony formation of pathogens near surfaces, in corners and crevices.