I get the idea (at least, as much as a layperson can) that a helium nuclei has less mass than the sum of its parts. That mass deficit is turned into energy. At this stage I feel like I've heard two things: that energy goes into holding the nucleus together or that energy is released in the fusion process.
So my question is, which is it? And if it's one of the above, where does the energy for the other originate?
At this stage I feel like I've heard two things: that energy goes into holding the nucleus together OR that energy is released (in the fusion process... I guess?).
It's both, if you admit a sloppy and misleading interpretation of "energy ... holding the nucleus together".
The fusion process releases energy, which winds up as kinetic energy of the reaction products. Therefore, the rest mass of the products is less than that of the reactants, since rest mass is simply total energy measured from the at-rest-relative-to-the-mass frame. To harvest fusion energy, one has to engineer a way to convert the reaction products' kinetic energy to whatever form you want it in.
Conversely, to break the helium nucleus apart by the reverse reaction, we have to put energy back into the system to make this happen. As nucleusses form from smaller parts in exothermic nuclear reactions, the strong nuclear force eventually overwhelms the initially repulsive electromagnetic force such that there is a nett release of energy, rather like a stretched spring's relaxing and thereby converting its potential to kinetic energy as it does so. To reverse the process, i.e. split the nucleus apart again or stretch the spring, energy has to be put back into the system and the reversal can't happen till this happens. It is in this sense that the "energy holds the nucleus together": an energy "debt" must be "repaid" before the inverse fission / string stretching process happens. The notion of a nucleus continuously doing work to hold itself together is wrong and unfortunately tends to be the way people read the statement "energy goes into holding the nucleus together". This was a common layperson's explanation in popular / childrens science books in the 1970s and 1980s that unfortunately would still seem to have life.
As in David Elm's answer, only relatively light nucleusses release energy through fusion. The most stable nucleusses of all, i.e. the ones with the lowest rest mass per nucleon and thus the most tightly bound nucleusses, are iron 56 and and nickel 62. Exothermic reactions for nucleusses heavier or lighter than these tend to be fission and fusion reactions, respectively.
Any time the potential energy of a system is reduced, the mass of that system is reduced by $m=\frac{E}{c^2}$.
The change in mass is ordinarily very small, so it really only becomes noticeable when that potential energy change is very large, as it with rearrangements of nucleons (protons and neutrons).
Sometimes putting nucleons together decreases the energy of the system (fusion), but sometimes nucleons splitting apart from each other decreases the energy (fission).
The excess energy goes into the kinetic energy of the products. To use the simple example of D-T fusion ($^2H + \,\!^3H \;\rightarrow \;^4He + n$), the two hydrogen nuclei have more total mass than the helium nucleus and neutron. However, the helium nucleus and neutron are moving faster than the hydrogen nuclei were, in such a way that the extra kinetic energy exactly balances the lost mass.
This example is artificial, but illustrative.
One always can take as given the energy conservation law:
$2\cdot m_pc^2 + 2\cdot m_nc^2 \rightarrow m_{4He}c^2 + E_x$
If this reaction happened this way (it does not, but never mind) $E_x>0$ the energy $E_x$ must dissipate somehow. Once it is away, you cannot brake the $^4$He, unless you bring $E_x$ back. From this point of view, you can name this missing energy $E_x$ the "binding energy".
One step forward - one can imagine the formation process like this:
$2\cdot m_pc^2 + 2\cdot m_nc^2 \rightarrow m_{4He^*}c^2 \rightarrow m_{4He}c^2 + E_x $
see $^4$He$^*$ - this stands for helium, that is (hypothetically) in an such an excited state, that it equally can form a stable $^4$He or dissociate again - just randomly - AND it's mass is not any lower that of 2p+2n. See- the excited state has different mass than the ground state.
The energy $E_x$ usually escapes with some particle or gamma (would be in this hypothetical case with energy $E_\gamma=E_x$) and the way it is removed must also obey a momentum conservation law.
