Until the time of Einstein, mass and energy were two separate things. In the special theory of relativity Einstein demonstrated that neither mass nor energy were conserved seperately, but that they could be traded one for the other and only the total "mass-energy" was conserved. The relationship between the mass and the energy is contained in what is probably the most famous equation in science,
E = m c 2
Because the speed of light squared is a very large number when expressed in appropriate units, a small amount of mass corresponds to a huge amount of energy. Thus, the conversion of mass to energy could account for the enormous energy output of the stars, but it is necessary to find a physical mechanism by which that can take place.
Einstein himself originally thought that it might be impossible to find a physical process that could realize the potentiality embedded in his equation and convert mass to energy in usable quantities. In the nuclear age, we now know (both for better and for worse) that he was too pessimistic; there are several physical processes that can accomplish this.
The stars are at enormous distances from us, yet we can see thousands in the sky without the aid of a telescope. This tells us that the stars are extremely luminous. We must then ask what the source of their enormous energy could be.
Given what we know about stars like the Sun, there are two possible sources of such energy: (1) gravitational contraction and (2) thermonuclear reactions that convert mass to energy. Both play important roles in producing energy over the lifetime of a star, but the primary reason for the long stable period of a star's life is thermonuclear fusion. This fundamentally involves the conversion of mass to energy. The nobel prize for understanding this process is stars was given to Hans Bethe in 1967. (Hans Bethe is now 95 years old and a retired professor at Cornell. At present he is still active, and still publishing research. His career will go down as one of the longest in the history of science. He published his first paper in 1927.)
There is a (perhaps purely apocryphal) story that near the time of his theoretical breakthough, Bethe was to have said to his companion on a romantic date (while looking out at the stars) "You know, my dear, I am the only one in the world who knows why those shine."