Does entropy really always increase (or stay the same)? 
Consider this image. If the big (grey) molecules were all to spontaneously move to the left, and the small ones were to move to the right, there would be an increase in order.
While unlikely, wouldn't this mean that entropy decreases?
 A: The molecules can assemble in one corner of the room. The point is that it's exceedingly unlikely to happen. It is so unlikely in fact, you will to best approximation never see it happening that all air molecules spontaneously assemble in the corner of a room even though it isn't forbidden by the laws of physics. But if you wait long enough, it will happen (provided some assumptions about the system hold). The entropy is a statistical measure that tells you simply that the most likely development of the system is one towards the most likely state. That is not in contradiction with it being in principle possible that there exist exceedingly unlikely fluctuations that temporarily restore some order.
Besides this, as Anna already pointed out, entropy can decrease of course in open systems. You should be more specific in your question about this.
A: Your example is an example of a microstate in your sample, which is a statistical ensemble and its entropy is defined by the number of microstates possible.

Where S is the entropy and K is the Boltzman constant and Ω is the total number of microstates. One of these microstates you show contributes to the Ω as one state. It will immediately flow into another one as the kinematics unfreeze from your frozen picture.
So, no it is not an example of an entropy decrease.
To decrease entropy in an open system is possible. Consider crystals drawn out of a liquid phase. There is energy given up and the crystal appears ordered from disorder. The entropy of liquid+ crystal , in a closed system, increases.
Live organisms continually decrease the entropy of their system, using chemical properties to release energy to the environment and increase the total entropy.
A: @WIMP is correct and @anna v is not correct.
To avoid side-issues, I will only talk about closed conservative systems.
The second law of thermodynamics is often misunderstood.  In fact and in law, entropy can decrease.  The second law is a statistical law, it talks about what the statistical expectation, or probability, is.  Entropy will almost certainly not decrease at any given point in time.  But over a sufficiently large interval of time, it is almost certain that there will be episodes of decrease.
It has been said, and I wish I knew a reference for this, that any group of scientists talking about entropy will be talking nonsense within ten minutes.  But Sir James Jeans and Sir Ralph Fowler are notable for their common sense in this matter.
Sir James Jeans said this (Here, $\phi$ is the entropy)

the machine of the universe, assuming its motion to be governed by the canonical equations of motion, is just as capable of running in one direction as in the reverse direction.  If it can pass from a state A to a state B, the equations of motion shew that it can also pass from a state B to a state A.  If the passage from A to B involves an increase of entropy, the passage from B to A must involve a decrease of entropy : in this latter motion heat will pass from the colder bodies to the hotter.
if we place a vessel full of water over a fire, it is only probable, and not certain, that the water will boil instead of freezing.  And moreover, if we attempt to boil the water a sufficient number of times, it is infinitely probable that the water will, on some occasions, freeze instead of boil.
Speaking loosely, it is just as likely that the water will freeze as that it will boil in any specified way.  There are, however, so many ways in which the water can boil, all these ways being indistinguishable to us, that we can say that it is practically certain that the water will boil.

J. H. Jeans, Dynamical Theory of Gases, 4th ed., Cambridge, 1925, pp. 181f.
===========
I left out Sir James's instructive analogy from cards, since although illuminating it is a parenthesis.  I now include it:

The analogy of the distribution of a pack of cards will help us to see further into the problem presented by the entropy of a gas.  In dealing cards, it is just as likely that the dealer will have the thirteen trumps as that he will have any other thirteen cards that we like to specify.  The occurrence of a hand composed of thirteen trumps might, however, be justly regarded as a 'coincidence', whereas the occurrence of any specified hand in which the cards were more thoroughly mixed, could not reasonably be so regarded.  The explanation is that there are comparatively few ways in which a hand which is all trumps can be dealt, but a great number in which a mixed hand can be dealt.

Now a precise specification of the individual cards in the hand is the microstate.  The general category "all trumps" or "mixed hand" is the macrostate.  The macrostate "all trumps" contains very few microstates, so it has a low entropy.  The macrostate "mixed hand" contains very many microstates, each one of which looks different when examined closely and specified completely, but they are all included in the general description "I don't got much".
The initial macrostate is "the dealer has a deck of cards and is about to deal four hands."  There are many ways this macrostate, which has maximal entropy, can evolve into dealing a mixed hand which is nothing special, a macrostate which has approximately the same entropy.  There are very few ways it can evolve to dealing the dealer all trumps, a state with much lower entropy.  (Since there are only 52 cards, the entropy actually does decrease a tiny bit.  If there were an infinite number of cards, i.e., if we were working in the thermodynamic limit, then the entropy of the undealt "pack of cards" would be exactly equal to the entropy of the state "mixed hand which is nothing special" and the entropy would not have decreased at all.)
see Clear up confusion about the meaning of entropy
