If entropy must increase for any real process and natural processes move from order to disorder then the early universe must have been "highly ordered". However, when I think of the extremely dense and hot singularity known as the big bang the word ordered doesn't come to mind. Can anyone help me make sense of this?
While the matter/energy contents of the universe started in a very high entropy state, the spacetime was apparently very smooth and hence low entropy. As the universe expanded not only did the bound on entropy increase (as J.G. points out) but it also allowed clumping of matter that increased the spacetime entropy but reduced the local matter entropy. Without gravity the universe would not have produced anything more than cooling gas.
It is worth noting that over time spacetime entropy will increase as more and more matter goes into black holes, up until the point where they evaporate. The "trick" here is that evaporation can increase the entropy of the universe if the universe is large enough (the number of microstates of the very sparse photon/lepton gas that remains is huge).