The stored energy in a spring is 1/2*K*x^2, so from an energy storage standpoint it would be best to have a spring that had a large deflection (high yield strength). This brings Titanium into the picture due to its very large yield point. It's possible carbon fiber would be pretty good from a weight ratio standpoint because it's so light, but it is also very stiff which means it wouldn't deflect very far before breaking (keep in mind the x^2 in the energy formula).
You'll basically have to do some calculation of a theoretical spring of certain dimensions made out of a specific material. You might consider analyzing a simpler spring like a leaf spring since a load will be taken in pue tension/compression in the beam, where as a coil spring tends to have a combination of bending and torsional sresses. It probably isn't useful to discuss a carbon nanotube spring, since they don't exist (and carbo nanotubes are best in tension, like carbon fiber).