The essential point is that energy has mass. The discovery of the equivalence of energy and mass was a fundamental one – and, despite its importance, it’s anything but obvious. As far as we know, that's just the way nature is built.
Adding energy to something (whether by kicking it to make it move, heating it, or raising it up and putting it on a shelf) therefore adds mass to it. Basically, every single constituent part of the object is now a bit heavier.
Compressing a spring involves doing some work (energy). The atoms in the spring are held in place by electromagnetic forces. These are as much part of the spring as the atom itself. Pushing the atoms closer together, or twisting groups of them out of their normal position, effectively stores energy in the electromagnetic fields between the atoms. And since the mass of the spring is comprised of the masses of everything in it – particles and fields – the mass of the spring is greater.
As KenG has said, confusion can arise because some teachers and textbooks use the words ‘mass’ and ‘matter’ interchangeably.
The basic particles of ordinary matter can, if it helps, be imagined as chunks of 'frozen' energy (this is just a rough way of thinking). And since energy has mass, the familiar particles of matter have mass. This mass, if the particle isn’t moving, is called its ‘rest mass’. Not everybody would like this description, but the basic idea is that there is no distinction between the energy that manifests itself as the rest mass of a particle, and other manifestations of energy, such as thermal energy or light energy. They are all energy.