Thinking about it, it makes sense if you think of a checkerboard whose squares are randomly painted white or black.
In such a case, there would be 2^64 possible states of "disorder", a high amount of entropy.
But if the checkerboard kept losing squares until there was only one, there would be 2^1 = 2 states of disorder, a low amount of entropy.
A black hole's entropy is thought to be described by the surface area of the event horizon. After the black hole is no longer being "fed", it begins to evaporate by radiating Hawking radiation.
As it evaporates, its surface area becomes smaller, analogous to the checkerboard losing squares, so the black hole's entropy also becomes smaller.
However, the Hawking radiation is quite hot so it increases the entropy of the space surrounding the black hole and as such, the total entropy of the "system" increases.
A less 'cosmic' example would be how gravity squeezes graphite (w/ 2 dimensional symmetry) into diamond (w/ 3 dimensional symmetry). The diamond has less entropy than the graphite. Gravity provided the energy to heat and press the atoms into a more ordered arrangement. But, like with the black hole, this process radiates much heat and so the overall entropy of the system increases. The localized decrease in entropy is surrounded by a region whose entropy has increased.
The universe, in effect, contains Maxwell's "demon" in a jail.