The answer is the there is some reduction in mass whenever energy is released, whether in nuclear fission or burning of coal or whatever.
However, the amount of mass lost is very small, even compared to the masses of the constituent particles. A good overview is given in the Wikipedia article on mass excess. Basically, the mass of a nucleus will in general be a little bit off from the sum of the masses of the protons and neutrons inside it. This is because there is a binding energy holding the nucleus together, and your standard $E = mc^2$ gives the equivalent mass for this energy.
In the fission of uranium-235,
$$ {}^{235}_{\phantom{0}92}\mathrm{U} + {}^1_0\mathrm{n} \to {}^{236}_{\phantom{0}92}\mathrm{U} \to {}^{141}_{\phantom{0}56}\mathrm{Ba} + {}^{92}_{36}\mathrm{Kr} + 3\ {}^1_0\mathrm{n}, $$
the total rest mass of the products is slightly less than of the reactants. This is true even though there are the same number of protons (92) and neutrons (144) before and after. So it is not as though an entire nucleus disappears, or even an entire proton or neutron. The lost mass comes from the binding energy.
The take-away message is that we are not destroying particles to create energy. Even nuclear fusion conserves the total number of protons and neutrons. Instead, you should think about the mass-energy equivalence the other way around. The fact that there is potential energy capable of being released in nuclear fission implies that the reactants must be heavier than the products. In the same fashion, a typical battery weighs less after being discharged (though by an immeasurably small amount), even though the nuclei are unchanged and the number of electrons is the same. That is, potential energy in any form adds to the mass of the system as a whole, and is not attributable to any one component.