Can someone give an intuitive way of understanding why Gauss's law holds? Gauss' Law of electrostatics is an amazing law. It is extremely useful (as far as problems framed for it are concerned :D. I do not have a real world-problem solving experience of using Gauss' Law).
However, I don't really understand why it works. What my doubt is, is this:

In the God-equation:
$$ \oint_s\vec{E}\cdot d\vec{s} = \dfrac{q_{enc}}{\epsilon_\circ} $$
$\vec{E}$ is the field at the area element $d\vec{s}$, and that field
  is due to all the charges in the configuration. But the $q_{enc}$ is
  the algebraic sum of only those charges that are enclosed within the
  Gaussian surface. That is, to the net flux, only those charges affect that are within the surface. The contribution of the outside charges somehow cancels out. Why does it work that way?

If I knew a lot of advanced math and vector spaces and such fancy stuff, I wouldn't have asked this question. I am looking for an intuitive way of understanding its proof - if it is possible to understand without that depth of math. I do know some basic integration and surface integrals and all that (otherwise I wouldn't be able to use Gauss's Law, obviously!). So, if your answer involves these things, I'd be fine. But please don't bring in the divergence theorem etc. I tried to decipher the math behind it on wikipedia, and didn't understand a thing.
 A: First, since both the electrostatic field and the integral are additive, it is (intuitively) enough to see that the law works for a point charge either inside or outside the surface. We can imagine adding all of the charge in the final configuration little by little -- if Gauss' law holds for each small increment, it is also going to hold for the sum.
So let's imagine a point charge and see how its Coulomb field (which has a nice simple shape) contributes to its surface integral. In particular, let's consider the part of the surface that lies within a thin cone with the point charge at its apex. The entire integral is then the sum of the contributions for enough such ("infinitesimally thin") cones to cover all directions we can look at the point charge from.
In the general case, if we make the cone thin enough it will look like simply a ray when we look at it from the scale of the surface. We can ignore the cones/rays that are ever tangent to the surface; they are too few to make a net contribution when we go to the limit. So by assumption each cone will cross the surface a well-defined number of times -- an odd number if the charge is inside the surface, and an even number if the charge is outside the surface.
Now each crossing between the cone and the surface contributes to the surface integral by precisely the same magnitude (though with different signs according to whether we're going into or out of the surface), no matter where this crossing happens. Since we're going to the limit, at the point of crossing the cone looks like a cylinder and the surface looks like a plane. If the crossing is far form the point charge, the area of the surface in the intersection is larger, but the field is weaker by exactly the right factor to cancel that out -- here it is crucial the the field is inverse square, it wouldn't work for any other shape of the field. The area of the intersected surface is also larger if the crossing happens at an oblique angle, but that is canceled out exactly by the cross product in the integrand.
Now if the charge is outside the surface, every cone crosses the surface an even number of times, which cancel out each other in pairs -- so each cone contributes zero to the total surface integral.
On the other hand, if the charge is inside the surface, there is one more outgoing crossing than incoming for each cone -- so each cone contributes to the surface integral in proportion to its solid angle. All the infinitesimal cones taken together have solid angles that add up to $4\pi$ steradians, so the total surface integral is the same no matter what the shape of the surface and where inside it the charge is located. It's obviously proportional to the strength of the charge too, and the various proportionality factors are then subsumed into the $\epsilon_0$ constant by definition.
A: I can give you an intuitive view from a physicist.
Charges are the sources and sinks for the electrical field. Consider the extreme case where the volume enclosed by the surface is empty space, so no charges. Then any field line that enters the volume must exit the volume somewhere else. Thus, the integral of the field over the entire surface is 0. 
If field lines only go in, but none come out, there must be a negative charge inside the volume (field lines end on negative charges), because the surface integral is negative. Vice versa, if they only come out, there must be a positive charge inside. It does not matter where the charge inside the volume sits exactly, because the same "amount of field lines" must come through the surface somewhere. 
In my first semester the way they taught it to us was actually by comparing it to fish that go through a closed net inside the sea, but I don't remember what they used as analogues for the sinks and sources. Basically, if there are a lot of fish coming out of your closed net, there must be a source of fish inside somewhere.
Apologies if this is too handwavey for this part of SE.
A: 
The contribution of the outside charges somehow cancels out. Why does it work that way?

Actually all the charges in the space (including the ones outside) do play role in that they contribute to the determination of $\vec{E}$ that you see on the left of the equation. The law is just a nice way to avoid complexity when dealing with multiple charges.
