Shear-thinning is an important rheological property of many biological fluids, such as mucus, whereby the apparent viscosity of the fluid decreases with shear. Certain microscopic swimmers have been shown to progress more rapidly through shear-thinning fluids, but is this behavior generic to all microscopic swimmers, and what are the physics through which shear-thinning rheology affects a swimmer's propulsion? We examine swimmers employing prescribed stroke kinematics in two-dimensional, inertialess Carreau fluid: shear-thinning "Generalized Stokes" flow. Swimmers are modeled, using the method of femlets, by a set of immersed, regularized forces. The equations governing the fluid dynamics are then discretized over a body-fitted mesh and solved with the finite element method. We analyze the locomotion of three distinct classes of microswimmer: (1) conceptual swimmers comprising sliding spheres employing both one- and two-dimensional strokes, (2) slip-velocity envelope models of ciliates commonly referred to as "squirmers" and (3) monoflagellate pushers, such as sperm. We find that morphologically identical swimmers with different strokes may swim either faster or slower in shear-thinning fluids than in Newtonian fluids. We explain this kinematic sensitivity by considering differences in the viscosity of the fluid surrounding propulsive and payload elements of the swimmer, and using this insight suggest two reciprocal sliding sphere swimmers which violate Purcell's Scallop theorem in shear-thinning fluids. We also show that an increased flow decay rate arising from shear-thinning rheology is associated with a reduction in the swimming speed of slip-velocity squirmers. For sperm-like swimmers, a gradient of thick to thin fluid along the flagellum alters the force it exerts upon the fluid, flattening trajectories and increasing instantaneous swimming speed.