In several biologically relevant situations, cell locomotion occurs in polymeric fluids with Weissenberg {number} larger than one. Here we present results of three-dimensional numerical simulations for the steady locomotion of a self-propelled body in a model polymeric (Giesekus) fluid at low Reynolds number. Locomotion is driven by steady tangential deformation at the surface of the body (so-called squirming motion). In the case of a spherical squirmer, we show that the swimming velocity is systematically less than that in a Newtonian fluid, with a minimum occurring for Weissenberg numbers of order one. The rate of work done by the swimmer always goes up compared to that occurring in the Newtonian solvent alone, but is always lower than the power necessary to swim in a Newtonian fluid with the same viscosity. The swimming efficiency, defined as the ratio between the rate of work necessary to pull the body at the swimming speed in the same fluid and the rate of work done by swimming, is found to always be increased in a polymeric fluid. Further analysis reveals that polymeric stresses break the Newtonian front-back symmetry in the flow profile around the body. In particular, a strong negative elastic wake is present behind the swimmer, which correlates with strong polymer stretching, and its intensity increases with Weissenberg number and viscosity contrasts. {The velocity induced by the squirmer is found to decay in space faster than} in a Newtonian flow, with a strong {dependence} on the polymer relaxation time and viscosity. Our computational results are also extended to prolate spheroidal swimmers and smaller polymer stretching are obtained for slender shapes compared to bluff swimmers. The swimmer with an aspect ratio of two is found to be the most hydrodynamically efficient.