Why do fusion and fission both release energy? I only have high school physics knowledge, but here is my understanding:
Fusion: 2 atoms come together to form a new atom. This process releases the energy keeping them apart, and is very energetic. Like the sun!
Fission: Something fast (like an electron) smashes into an atom breaking it apart. Somehow this also releases energy. Less energy than fusion, and it's like a nuclear reactor.
Now my understanding is that the lowest energy state is when everything is tightly stuck together (as per fusion), and it costs energy to break them apart.. 
So.. why do both fusion and fission release energy?
 A: In general, both fusion and fission may either require or release energy.
Purely classical model
Nucleons are bound together with the strong (and some weak) nuclear force. 
The nuclear binding is very short range; this means that we can think of nucleons as "sticking" together due to this force.
Additionally the protons repel due to their electric charge.
As geometry means that a nucleon has only a limited number of other nucleons it can "stick" to, the attractive force per nucleon is more or less fixed.
The repulsive electric field is long range. That means that as the nucleus grows, the repulsion grows, so that eventually that repulsion exceeds the attractive effect and one cannot grow the nucleus further. Hence a limited number of possible elements.
Effectively this means the attractive force per nucleon increases rapidly for a small number of nucleons, then tops out and starts to fall.
Equivalently, the binding energy per nucleon behaves similarly.
As @cuckoo noted, iron and nickel have the most tightly bound nuclei; iron-56 having lowest mass per nucleon and nickel-62 having most binding energy.
This image (from Wikipedia) illustrates the curve in the typically presented manner:

However, I prefer to think of binding energy as negative and therefore better visualize iron as being the lowest energy state:

For lighter elements:


*

*Fission requires energy 

*Fusion releases energy


For heavier elements, the opposite is true.
The reason we mainly observe the release energy cases is because:


*

*It is easier to do

*It is more "useful" 

A: I think it's worth specifically addressing the word 'both' in the question. If you say 'both release energy', you're implying some contradiction, but there actually isn't any such issue. You're comparing apples and oranges.
For a substance which has an endothermic fusion reaction, the fission of that substance will probably be a net exothermic process. This is applicable for elements heavier than Iron.
For elements with exothermic fusion reactions, the opposite is true. So eventually, for a given element, only one of the two processes (fission and fusion) will be a net exothermic process. You could also look at this Physics SE post: Are all nuclear fusion reactions exothermic and fission reactions endothermic?
A: Because attraction of the strong nuclear force has a short range, while electrostatic repulsion has a long range.
As a consequence, electrostatic repulsion will grow faster with number of nucleons than nuclear attraction (protons throughout the nucleus will repel each other, while only neighboring nucleons will attract). This causes less binding energy per nucleon as their number increases and at some point this reaches maximum and starts to decrease. 
Iron just happens to be at the maximum of the binding energy per nucleon. Therefore, for heavier elements than iron, fission releases energy, while for lighter elements than iron, fusion releases energy.
This can't be completely circumvented by adding more neutrons, mainly because weak nuclear force makes them unstable, but it works to some degree, which is why heavier nuclei usually have higher neutron to proton ratio. But at some point it is no longer possible to add more nucleons without making the whole thing unstable, which is why very heavy elements are radioactive.
A: Fission releases energy, because a heavy nucleus (like Uranium-235) is like a cocked mouse trap: it took energy to squeeze all those protons and neutrons hard enough together to make them barely stick (by the nuclear force) against the natural tendency for all those protons to fly violently apart because of their electrostatic repulsion. When struck by an incoming neutron, it is like a mouse touching the trigger pedal of the trap: BANG goes the nucleus. 
In the case of fusion, the mechanism is different: the nuclear force between protons and between neutrons is very powerfully attractive but only kicks in when the particles are so close to each other that they are "touching". That attraction is not quite enough to stick two protons together against their electrostatic repulsion but if you add two neutrons to the recipe, you get enough mutually attractive nuclear force to overcome electrostatics and the particles then violently suck themselves together with a very powerful BANG. 
Other fusion reactions in which the (2 protons plus two neutrons) get pressed onto a heavier nucleus (like carbon, nitrogen, oxygen, fluorine, ...) release progressively less energy, because it takes more and more work input to overcome the repulsion effect as the nucleus accumulates more protons. By the time you get to iron, further fusion reactions actually consume energy instead of releasing it, because the electrostatic repulsion effect gets bigger and bigger- and you are in the province of fission instead.
A: Here is a qualitative view.
The net energy is positive only for fusion of elements lighter than iron, i.e. energy is released by fusion. For elements heavier than iron, fusion consumes energy, i.e. the net energy is negative.
We can use fission today to release energy due to the fact, that some process in the past (e.g. in a supernova) put energy into the heavy nuclei.
A: Your assumption about the lowest energy state when everything is tightly stuck together is incorrect.
It only goes this way until you get iron nuclei - and this is why iron is the heaviest element created by fusion.
Creating nuclei heavier than iron consumes energy rather than releasing it. And this is why these elements are only created in supernova explosions and other highly energetic events where there is abundant energy input.
A: Fusion works by banging together the same two elements and sticking them together to form a new heavier element. When you add the masses of the two original elements it is greater than the new element. 
It is this mass difference that becomes energy.  You can calculate the amount of energy from Einstein famous equation E=mc(squared). Here m is (2 x Mass of original element) - (Mass of new element) and c is the speed of light.
Example: Two Hydrogen atoms together form one Helium atom.
When the mass of the two original elements becomes heavier the difference between their masses and the new element gets smaller.
Fission works by splitting one element into two new lighter elements. When you add the masses of the two new elements it is less than the original element.  
It is this mass difference that becomes energy.  You can calculate the amount of energy from Einstein famous equation E=mc(squared). Here m is (Mass of original element) - (Mass of new elements) and c is the speed of light.
I wanted to mention that is technically much more complicated than what I say here. The short answer is still the same: Mass is converted into Energy.
A: There's energy involved in keeping atoms apart, but also energy involved in holding an atom together. When you smash an atom, this bonding energy is released.
In fact, one of the four fundamental forces is responsible for binding atoms together - the strong nuclear force.
A: I wanted to add another answer to show an important plot - binding energy per nucleon versus the atomic number (number of nucleons [protons + neutrons]).

The binding energy is the amount of energy required to break apart a nucleus. If, after a change, the amount of binding energy decreases, we must have supplied energy to break apart a nucleus. If, on the other hand, it increases, it must have released energy.
We can see from the plot that there are two ways to increase the binding energy per nucleon: first, start from the right, beyond iron, and break apart nuclei, moving to the left and up the slope. This is fission. Second, starting from the left, fusing nuclei together, climbing up the slope towards the right. This is fusion. You can see that the rewards are particularly big if you go from hydrogen to helium. 
So, I guess the question now is: why isn't the plot monotonic? Why isn't it either always increasing or always decreasing? I think the other answers have already shed light on that.
A: Wanted to provide a quick answer, but apparently now is frowned upon to give quick answers in comments, so here it is:
Roughly speaking, nuclear fission is endothermic for nuclei where nuclear fusion would be exothermic, and viceversa. For nuclei smaller than Iron, fission is typically endothermic, while fusion is exothermic. For nuclei heavier than Iron, the situation reverses.
A: Fusion:
In a small nucleus there is a relatively large fraction of 
nucleons at the surface, which lowers the total binding energy.
The fusion of 2 very small nuclei to one medium-sized nucleus releases energy,
mainly because in the resulting bigger nucleus
there are fewer nucleons at the surface than before.
This is analogous to the surface tension effect by which two water drops can
fuse and release some energy due to the lowered total surface area.
Fission:
In a big nucleus there is much Coulomb repulsion due to the many protons.
The fission of a very big nucleus into 2 medium-sized nuclei releases energy,
mainly because the total Coulomb repulsion within the 2 resulting
nuclei is smaller than before.
Therefore, medium-sized nuclei (~ 55 nucleons) have the biggest binding energy per nucleon.
The Bethe-Weizsäcker formula for the binding energy of a nucleus
gives a more quantitative explanation for this.
