As I understand it, entropy (and disorder) always increase, but gravity increases order. How does physics explain this? Examples of ordering by gravity:  The disordered cosmic dust collects into planetary systems.  Planets collect the heavier elements at their cores and the lighter elements above.  On Earth, iron collects at the core, water is pushed to the surface, and the lighter elements are pushed into the atmosphere.  Gold collects in veins, and diamonds and other crystals are created in the heat and pressure caused by gravity.  in fact, all of the inorganic order we encounter in life was caused by gravity. One could even say that gravity is one of the forces that brought order out of the chaos of the Big Bang.
PS: An typical example of entropy/disorder increasing is a teacup falling from a table and smashing to pieces on the floor.  It is easy to explain how the teacup flew apart, but difficult/impossible to explain a process where the teacup reassembles itself and jumps back onto the table.  However, in nature there is a process where something very similar happens routinely.  It is where billions of suns in the distant past explode into atoms and reassemble under the influence of gravity into newer suns with heavier atoms in the future.
 A: Gravity can appear to increase order, but it doesn't violate the second law of thermodynamics. For example, take a gas cloud at uniform density and temperature $T_1$ as our system. If we let it condense under its own gravity we can consider two cases:
(1) Assuming it forms a gas giant quickly without radiating any heat (i.e. adiabatically), it will have a higher final temperature $T_2$. The change in entropy in this case is matched by the increase in temperature. Note that by our assumption total energy of the system is conserved (gravitational potential energy is converted to thermal kinetic energy- see Kelvin-Helmholtz mechanism).
(2) Assuming it collapses quasi-statically, radiating heat to gravitationally collapse at the same initial temperature $T_1$, then the final entropy of the (open) system is indeed lower than the initial entropy: 
\begin{equation} \delta S_{system} = \frac{\delta Q}{T_1} < 0 \end{equation}
However, the heat lost will increase the entropy of the surroundings, maintaining constant entropy in the universe:
\begin{equation} \delta S_U = \delta S_{system} + \delta S_{surroundings}=0 \end{equation}
Gravity increases order at the expense of equal or greater disorder via thermal motion, either inside the system (adiabatic case 1) or via heating of the surroundings (isothermal case 2). Thus gravity obeys the second law of thermodynamics.
