First of all the socalled permittivity of the vacuum is a unit-conversion factor in the SI. In more natural systems of units [itex]\epsilon_0=\mu_0=1[/itex] and you put appropriate factors [itex]c[/itex] or [itex]1/c[/itex] into the Maxwell equations (sometimes with factors [itex]4 \pi[/itex]), leading to rationalized and usual Gaussian units. E.g., in rationalized (Heaviside-Lorentz) units, the Maxwell equations (in a vacuum) read
[tex]\vec{\nabla} \times \vec{E}+\frac{1}{c} \partial_t \vec{B}=0, \quad \vec{\nabla} \cdot \vec{B}=0,[/tex]
[tex]\vec{\nabla} \times \vec{B} - \frac{1}{c} \partial_t \vec{E}=\frac{1}{c} \vec{j}, \quad \vec{\nabla} \cdot \vec{E}=\rho.[/tex]
For the usual Gaussian units you simply mulitply the sources on the right-hand side of the latter two equations by [itex]4 \pi[/itex]. In these units the electric and the magnetic fields have the same dimension as it should be from a relativistic point of view. This is somewhat cumbersome to use in everyday life of an electrician, because the units of usual currents become somewhat unhandy to handle.
Thus one has invented the international system of units, where you always have to carefully keep track of the constants [itex]\epsilon_0[/itex] and [/itex]\mu_0[/itex]. There is, fortunately, only one arbitrary factor in this choice of units, because one necessarily has [itex]c=1/\sqrt{\mu_0 \epsilon_0}[/itex].
If you put a charge in a dense medium you have to consider the reaction of this medium to the electric field of this charge. Take a non-conducting di-electric. It consists of a lot of atoms or molecules, which themselves are build of an atomic nucleus (atomic nuclei) and surrounding electrons, bound to the nucleus. Then the electric field of the added charge causes the negatively charged electrons to be shifted a bit relative to the positively charged nuclei, which leads to a little (additional) polarization of the atoms or molecules and thus the whole medium. Usually the electric fields of such external sources are weak compared to the electric fields binding the electrons and atomic nuclei together. This implies one can do "linear-response theory", i.e., you can assume that the polarization is linear to the extra "external field" brought into the system by the additional charges. Finally you introduce the macroscopic field [itex]\vec{D}=\epsilon \vec{E}[/itex] and lump all the complicated interactions of the fields and the interactions of the extra charges + charges constituting the medium on average to a consitutive constant [itex]\epsilon[/itex]. Then [itex]\vec{\nabla} \cdot \vec{D}=\rho,[/itex] where [itex]\rho[/itex] is the averaged distribution of the additonally brought in charges.
For an excellent introduction to this relation between the fundamental "microscopic" Maxwell equations with the "macroscopic" Maxwell equations and the constitutive relations, see
J. Schwinger, Classical Electrodynamics