In order for a process to happen, it has to increase the combined entropy of the system in which it happens and of the surrounding (2nd law of thermodynamics). As we will see in a bit, the more work the process does on the surroundings, the less the entropy of the surroundings increases, putting a limit on how much work the process can do.
What happens to the energy leaving a system?
When a process brings the system from a higher to a lower energy, the energy leaves the system in the form of work done on the surroundings or heat transferred to the surroundings (1st law of thermodynamics). For a given set of initial and final states, the amounts of work and heat can vary, but the sum has to be the same. For example, if our system is a charged battery, we can either run a motor with it, lifting up a rock (work done on the surrounding). Or we can short the battery, creating thermal energy that is transferred to the surrounding in the form of heat. We can even have a situation where heat and work have opposite signs (e.g. do more work and have heat transferred into the system to get the same energy balance).
How is heat and work related to entropy changes?
The change in entropy inside the system depends solely on the initial and final state. For the surrounding (with nothing else going on in the surrounding), the change in entropy depends on the heat transferred. The more heat is transferred to the surrounding, the more the entropy of the surrounding increases. To maximize the work, you want to minimize the heat transferred to the surroundings (or even transfer heat to the system), but only to the point the that total entropy still increases (otherwise the process could not run). So if you match the entropy change in the system with the opposite entropy change in the surrounding (via heat exchange), you get the maximum work out of your process.
Can I see a picture?
Sure. The picture shows that the sum of heat and work is equal to the enthalpy change of the system. Values shown with a downward arrow are negative and with an upward arrow positive. For heat and work, negative values mean energy is transferred out of the system. For example, work done by the system on the surrounding is a downward arrow, and exothermic reactions have a downward arrow for $\Delta H$.
The picture also indirectly shows the entropy (via the arrows labeled heat and $-T \Delta S$. If the arrow for $-T \Delta S$ is downwards, entropy in the system increases (scenarios labeled "more dispersed"). If the arrow for heat is downwards, entropy in the surrounding increases. To calculate the actual entropy, you would have to divide by the temperature, but the way it is shown everything can go into a single picture.
I have three scenarios, depending on whether the process is exothermic or endothermic and whether the entropy in the system increases or decreases. One scenario (endothermic reaction with a decrease of the system's entropy) is not shown (you would have to do work on the system to drive such a process, and we are trying to make the process do work for us instead).
In scenario 1, the process is exothermic. Some of that available energy is transferred in the form of heat (to make sure that the overall entropy does not decrease) and some of it is transferred in the form of work done by the system.
In scenario 2, the process is also exothermic, but different from scenario 1 the entropy of the system increases in this scenario. The work done by the system is (surprisingly, perhaps) larger than the enthalpy change, and the extra energy comes from heat transfer from the surroundings.
In scenario 3, the process is endothermic. You might think that this process can't do any work because - where would the energy come from? It comes from the surrounding, partially to provide the energy for the endothermic process and partially to be transferred back into the surrounding in the form of work. This can happen because just as in scenario 2, the entropy of the system increases.
[...]the Gibbs free energy is the maximum amount of work (or useful work) that a system can do, whereas entropy is a measure of the non-available enthalpy.
This sort of describes scenario 1, which I pasted again below with two boxes for emphasis.
The pink box represents the 1st law of thermodynamics. There is some enthalpy available from the process, and this will leave the system either as work or heat or some combination, as long as it adds up to the enthalpy change in the system. The blue box represents the 2nd law of thermodynamics. The entropy increase of the surrounding (through transfer of heat to it) has to be larger or equal to the entropy loss in the system. If you combine the two laws, you get the maximum work the system can do. In this scenario, the change in entropy of the system times the temperature represents that portion of the enthalpy not available for work (labeled $-T \Delta S$ in the diagram). You can't, however, use that label in the other scenarios where the entropy of the system increases. In those scenarios, the entropy change in the system results in more work available than the enthalpy change would suggest.
This is all rather complex and might make you dizzy. The Gibbs energy helps us to summarize all this in a single quantity. It combines entropy and enthalpy changes in the system in a neat way that tells us about the maximum work. In the absence of work, it also tells whether the process will happen in that direction or not.
Disclaimer for those that have a physical chemistry background
This is for a closed system at constant pressure and temperature (i.e. P-V work is done against a constant pressure, and initial and final state have the same temperature). Whenever it says work, it refers to non-P-V work only. Labels $\Delta H$, $\Delta G$, $\Delta S$ should read $\Delta H_\text{sys}$, $\Delta G_\text{sys}$, $\Delta S_\text{sys}$.
