We have studied the poorly understood process of flow-induced structure formation by colloids suspended in shear-thinning fluids. These viscoelastic fluids contain long flexible chains whose entanglements appear and disappear continuously as a result of Brownian motion and the applied shear flow. Responsive particle dynamics simulates each chain as a single smooth Brownian particle, with slowly evolving inter-particle degrees of freedom accounting for the entanglements. The colloids mixed homogeneously in all simulated quiescent dispersions and they remain dispersed under slow shear flow. Beyond a critical shear rate, which varies depending on the fluid, the colloids aggregate and form flow-aligned strings in the bulk of the fluid. In this work we explore the physical origins of this hitherto unexplained ordering phenomena, both by systematically varying the parameters of the simulated fluids and by analyzing the flow-induced effective colloidal interactions. We also present an expression for the critical shear rate of the studied fluids.