We'll keep it simple and say energy is the same thing as heat (not entirely true, but for the sake of this explanation it will suffice).
When you boil water, the H2O molecules go from a liquid state to a gas state. To do this, you need to heat the water up. The boiled water (now in a gaseous state) is really hot and can be considered full of potential energy.
Conversely, you would need to lower the temperature of water considerably to form ice. This would require a loss of heat, and thus, a loss of potential energy.
Hope this makes sense.