When you stretch a rubber band there is considerable deformation to the polymer molecules in the rubber. As a result some of the work you do on the rubber band goes into exciting molecular vibrations i.e. heat. Some of the work you do is stored as elastic energy and some is dissipated as heat.
As the band is allowed to relax the elastic energy stored within it does work on you. However, as before some of this energy goes into molecular vibrations and some into heat.
In both cases the work is the integral of force with distance, i.e. the area under a force-distance graph, however this graph will show some hysteresis due to the energy that is dissipated as heat:

Because of the hysteresis you don't get as much work out as you put in and the net work is not zero.
In the case of permanent deformation the physics is basically similar, except that the difference between the extension and relaxtion force-distance curves is greater so more work is lost as heat.