A stretched spring doesn't have more energy, though - I'm assuming you're speaking of a spring stretched to the point of distortion - because once you stop stretching it there's no energy there. And potential energy doesn't increase mass. If I put two similarly massive balls on shelves of different heights, the ball on the higher shelf isn't going to weigh more. And, actually, it's not going to weigh more as it's falling - there hasn't been any energy added to the system of the ball itself. It's simply attracted to the earth.
You're missing the point. The ball itself as an isolated system doesn't have more mass. But the system of Earth plus ball does. The change of position of the ball in the gravitational field of the Earth (and vice versa) requires energy. By imparting that energy to the system you increase its total mass (the rest mass of the system seen as a whole).
I don't know what you mean by the spring. Once stretched past the equilibrium point by any amount it has elastic potential energy. If you stretch too much and distort the material so that there is no more restoring force - then there is no elastic potential energy (it went into changing the shape of material, so in this sense it's still there but in a different form).
This isn't news, guys. It's what E=mc^2 says. In fact, forget the c^2 - it's just a unit conversion factor. You can choose units where it's equal to 1, so that you just get E=m.
The energy content of the system determines its mass. More energy in the system means it's more massive. Hot objects are heavier than cold, bound objects are lighter than their constituent parts, a box full of light weighs more than an empty one etc.