The question is dealt with in some detail in this article by John Baez.
Although the article assumes only a basic understanding of physics it's probably a bit too much for the non-physicist so I'll summarise. As a gas cloud collapses the particles within it are confined to a smaller volume of space so the entropy associated with their position (call this $S_P$) goes down - basically the system gets more ordered. However as the cloud collapses it heats up and the entropy associated with the temperature (call this $S_T$) goes up. The collapsed cloud will eventually cool down of course, but that just transfers the entropy $S_T$ to the photons radiated out into space. Anyhow, the total entropy change for the collapse will be:
$$ S_{total} = S_P + S_T $$
and we know that $S_P \lt 0$ and $S_T \gt 0$ so the two terms cancel each other.
Only John Baez shows that they don't cancel completely and the total entropy still goes down and this is, as you say, a violation of the second law.
What's missing from the calculation is the entropy associated with the gravitational field. There have already been various question related to this, for example Is the flatness of space a measure of entropy?, but I suspect these will be largely incomprehensible to the layman. Suffice to say that the infalling matter increasing the strength gravitational field associated with it, and this increases the entropy. Include this term and the total entropy is positive so the second law is not violated.
The ultimate limit of this is to form a black hole. Even though a (classical) black hole is completely characterised by just three parameters, mass, spin and charge, a black hole has the maximum entropy possible for the volume of space it occupies.