If you are talking about a small scale experiment, rather than the universe, then gravity is just a force like any other. You need to look at the total entropy change in an experiment, not just one part. You could make an analogy with the electromagnetic force, which is responsible for allowing chemicals to form, and for them to condense into solids and liquids. A solid is a lower entropy phase than a liquid. But when a liquid freezes into a solid, energy is released into the surroundings, increasing the entropy of the surroundings. The liquid will only freeze if the ambient temperature is below the freezing/melting point. If you look into the thermodynamic definition of temperature, this means that the liquid will only freeze if the energy released by the solidification will increase the entropy of the environment more than the decrease of entropy in the solidification.
Now, apply this same thought to gravity. Clumps form in a nebula and accrete into solar systems. But this must release energy, since the gravitational potential energy has decreased. The solar system is more ordered, but the energy increases the entropy elsewhere. It's only possible for these clumps to form if the temperature is low enough.
Consider the extreme: black holes. Black holes have an opposite temperature-energy relationship to most things. When you add energy to a black hole, the temperature goes down. Black holes of macroscopic size have very low temperatures. Temperature determines the direction which energy must flow to increase the entropy. Since the black hole is colder than the surroundings, total entropy increases as you feed matter into a black hole. (Energy flows spontaneously from hot to cold.) The surroundings get colder as it loses energy, but the black hole also gets colder as it gains energy, so the black hole will continue to eat up all the energy in the universe until there is very little energy left outside black holes. This is perhaps the state of maximum entropy. But who knows what dark energy does to the equation?