How does the voltage source provide energy in a circuit? I understand that a voltage source drives the current to flow from the terminal with lower potential to the terminal with higher potential. However, if the electrons are gaining potential energy then how can it also be supplying energy to the circuit? 
 A: 
However, if the electrons are gaining potential energy [...]

Actually, they are not.

[...] then how can it also be supplying energy to the circuit?

There indeed is a reduction in potential energy, transformed into kinetic energy.
It all comes down to the answer to your first line:

I understand that a voltage source drives the current to flow from the terminal with lower potential to the terminal with higher potential. 

This is correct. But. Two types of charges exist. A positive and a negative. What would happen if you suddenly replaced all negative charge-carriers with positive charge-carriers?
The flow will be opposite. The battery is creating a high negative net charge at one terminal, which is the reason that electrons are repelled and want to move away from this end towards the other end. Had they been positive, then they would be attracted to this terminal instead. The current flow would be opposite. In some circuits (most common ones with metallic wiring) the current flow is made from electrons. In others (semiconductors, ionic solutions, etc.) it is made from positive charges (or a mix). So it is not an irrelevant consideration.
So, which terminal is the "high-potential" one and which is the "low-potential" one? You are thinking, that a charge flowing from a low to a high potential must gain energy - but clearly, electrons moving one way or positive charges moving the other way, gives the same final result - energy will be spent as they move through the circuit in the same manner. They are two equivalent ways of thinking of the circuit.
Which do we call high and which low potential? People in the past have made the decision to always name it as if the charge-carrier was positive. The terminal (or point in the circuit) of higher potential is thus the terminal positive charges will move away from - and a "lower potential" point is a point that attracts positive charges. Regardless of what the actual sign of the charge is. This is a convention, so we didn't have to think in charge-carriers all the time.
So it is correct to think that the "high potential" battery terminal actually is a "low potential" point for the electrons. Because they loose energy on their way to that point. Like a ball falling from high potential on a shelf to low potential on the flow. We just don't say this conventionally. But keep it in mind, and then you always understand what potentials mean.
