How is Gauss' Law (integral form) arrived at from Coulomb's Law, and how is the differential form arrived at from that? On a similar note: when using Gauss' Law, do you even begin with Coulomb's law, or does one take it as given that flux is the surface integral of the Electric field in the direction of the normal to the surface at a point?
 A: Let us for simplicity consider $n$ point charges $q_1$, $\ldots$, $q_n$, at positions $\vec{r}_1$, $\ldots$, $\vec{r}_n$, in the electrostatic limit, with vacuum permittivity $\epsilon_0$. 
Now let us sketch one possible strategy to prove Gauss' law from Coulomb's law:


*

*Deduce from Coulomb's law that the electric field at position $\vec{r}$ is
$$\tag{1} \vec{E}(\vec{r})~=~ \sum_{i=1}^n\frac{q_i }{4\pi\epsilon_0}\frac{\vec{r}-\vec{r}_i}{|\vec{r}-\vec{r}_i|^3} .  $$

*Deduce the charge density
$$\tag{2} \rho(\vec{r})~=~\sum_{i=1}^n q_i\delta^3(\vec{r}-\vec{r}_i). $$

*Recall the following mathematical identity 
$$\tag{3}\vec{\nabla}\cdot \frac{\vec{r}}{|\vec{r}|^3}~=~4\pi\delta^3(\vec{r}) .$$
(This Phys.SE answer may be useful in proving eq.(3), which may also be written as $\nabla^2\frac{1}{|\vec{r}|}=-4\pi\delta^3(\vec{r})$).

*Use eqs. (1)-(3) to prove Gauss' law in differential form 
$$\tag{4} \vec{\nabla}\cdot \vec{E}~=~\frac{\rho}{\epsilon_0} .$$

*Deduce Gauss' law in integral form via the divergence theorem.
A: @Qmechanic's already provided a nice answer.
I would like to provide another one. 
Consider a charge $q$ be enclosed by any surface (not necessarily a sphere).
Something like this - 

Now, you write the flux coming out of this weird surface - 
$$
\phi_E = \displaystyle \oint_S \mathbf{E} \cdot \mathrm{d\mathbf{S}}
$$
We know that -
$$
\mathbf{E} = E \vec{r} = \dfrac{1}{4\pi \epsilon_0} \dfrac{q}{r^2}\vec{r}
$$ 
So, here in this weird surface. there is no fixed radius, is there? And the surface area that is considered here is not a continuous one.
So, I would get - 
$$
\phi_E = \dfrac{q}{4\pi \epsilon_0} \displaystyle \oint_S \dfrac{\mathrm{d\mathbf{S}}}{r^2} \tag{1}
$$
Recall that the term $\dfrac{\mathrm{d\mathbf{S}}}{r^2}$ is the very definition for the steradian - which is equal to $\dfrac{1}{4\pi}$ of a complete sphere. This holds good for any surface.
Simply put, this is the 3D analogue of the $2\pi$ rotation in a circle.
Here, we have its differential element, i.e, $d\Omega = \dfrac{\mathrm{d\mathbf{S}}}{r^2}$
Integrating it entirely, we have
$$
\displaystyle \oint_S \dfrac{\mathrm{d\mathbf{S}}}{r^2} = \displaystyle \oint_S d\Omega = 4\pi$$
Plugging this back into (1), we have - 
$$
\phi_E = \dfrac{q}{\epsilon_0}
$$
Which implies -
$$ \displaystyle \oint_S \mathbf{E} \cdot \mathrm{d\mathbf{S}} = \dfrac{q}{\epsilon_0}
$$
Ok, since we're done with deriving the integral form of Gauss's law (Which holds true for any closed surface), the following differential form can be obtained by applying the divergence theorem -
$$
\nabla \cdot \mathbf{E} = \dfrac{\rho}{\epsilon_0}
$$
A: @Qmechanic's proof is a nice general way to prove Gauss Law from Coulumb's Law.However I would like to add a simpler proof which I discovered on YouTube.

Source:https://www.youtube.com/watch?v=X_CHPTZfUGo
A: vs_292, just missed a small point.The dot product.The surface $ds$ should be along the electric field i.e along $\bf{r}$ (position vector).
Proof of Gauss' theorem (with solid zero):
$$\phi = \frac{q}{\epsilon_0}$$
$$d\phi = \vec{E}\cdot d\vec{s}=E\hat{r}\cdot d\vec{s}$$
$$phi = \oint_\limits{s}E\hat{r}\cdot d\vec{s}$$
Here this is the projection of $d\vec{s}$ along $\hat{r}$.
$$d\Omega = \frac{ds'}{r^2}$$
$$\phi = \oint_\limits{s} Eds' = \oint_\limits{s}\frac{1}{r\pi\epsilon_0}\cdot\frac{q}{r^2}ds'$$
$$\Rightarrow\phi=\frac{1}{r\pi\epsilon_0}q\oint_\limits{s}\frac{ds'}{r^2}$$
$$\Rightarrow\phi = \frac{1}{4\pi\epsilon_0}q\oint_\limits{s}d\Omega$$
$$\boxed{\Rightarrow\phi = \frac{1}{4\pi\epsilon_0}q4\pi = \frac{q}{\epsilon_0}}$$
Accompanying picture for the diagrams:

Source: Edupoint Youtube Channel.
