How did Williard Gibbs come up with the Gibbs equation?
He derived this formula by fully appreciating the fact that entropy tends to a maximum.

As the first paragraph of the relevant paper says,


  It is an inference naturally suggested by the general increase
  of entropy which accompanies the changes occurring in any
  isolated material system that when the entropy of the system
  has reached a maximum, the system will be in a state of equilibrium.
  Although this principle has by no means escaped
  the attention of physicists, its importance does not appear to
  have been duly appreciated. Little has been done to develop
  the principle as a foundation for the general theory of thermodynamic
  equilibrium.


That is to say, he saw it as obvious that entropy increases until it cannot increase anymore and this makes a for a good definition of equilibrium. Gibbs offers a second definition of equilibrium, however, by saying,


  For the equilibrium of any isolated system it is necessary and
  sufficient that in all possible variations of the state of the system
  which do not alter its entropy, the variation of its energy shall
  either vanish or be positive.


The new move, however, is to construct some kind of function which makes these two definitions simply the same definition stated in a different way. That is, Gibbs has introduced two conditions:

$$(\delta S)_{\epsilon} \le 0$$
$$(\delta\epsilon)_{S} \ge 0$$

In words, at equilibrium a system's entropy (for a constant amount of energy) can only change by decreasing, and at equilibrium a system's energy (for a constant entropy) can only increase. Or simply, entropy is a maximum and energy is a minimum.

Then, because these two properties are opposites in the sense that one tends to a maximum and the other a minimum, it is a reasonable thing to subtract them and say that when this subtraction is equal to zero, we are at equilibrium. This is exactly what Gibbs did. He literally just multiplied the entropy by temperature without justifying it ($TS$ is common on thermodynamics though so he may have thought it obvious), and wrote down:

$$\psi=\epsilon-TS$$

where in this case $\psi$ is what we now call the Gibb's free energy. With this definition, the two conditions for equilibrium above are turned into one condition which is,

$$(\delta\psi)_T \ge 0$$

That is to say, at a constant temperature physical systems tend to the minimum of a free energy surface.

The reasoning Gibbs' has walked through thus far is sufficient to derive the equation as you have written it if we say that $\epsilon=\epsilon(U,P,V)$. That is, the energy of the system is determined fully by the internal energy (imagine microscopic motions) and the pressure on the substance and volume of the substance. Then we can simply write (again he just guesses a proportionality of one and uses units to figure out the rest),

$$\zeta=U+PV-TS=H-TS$$

where $\zeta$ is again the Gibb's free energy in a more explicit form. He takes the next couple of pages to take the total differential and then simple integration would give the familiar form but this is just a mathematical exercise not worth going through here.

A more formal, but not much more complicated, derivation of Gibbs' energy from the same condition that entropy increases can be found here under free energy of reactions. In this case two conditions for the entropy are used. Namely, the internal and external entropies. That's worth looking at as it contains the same principle which Gibbs used.