Many micro-organisms find themselves immersed in fluids displaying non-Newtonian rheological properties such as viscoelasticity and shear-thinning viscosity. The effects of viscoelasticity on swimming at low Reynolds numbers have already received considerable attention, but much less is known about swimming in shear-thinning fluids. A general understanding of the fundamental question of how shear-thinning rheology influences swimming still remains elusive. To probe this question further, we study a spherical squirmer in a shear-thinning fluid using a combination of asymptotic analysis and numerical simulations. Shear-thinning rheology is found to affect a squirming swimmer in non-trivial and surprising ways; we predict and show instances of both faster and slower swimming depending on the surface actuation of the squirmer. We also illustrate that while a drag and thrust decomposition can provide insights into swimming in Newtonian fluids, extending this intuition to problems in complex media can prove problematic.