When exactly do we substitute $\epsilon_0 \rightarrow \epsilon$ and $\mu_o \rightarrow \mu $? If everything is embedded into vacuum, why aren't Maxwells Equations always with $\mu_o$ and $\epsilon_o$?
When exactly do we have to make the substitution  $\epsilon_0 \rightarrow \epsilon$ and $\mu_o \rightarrow \mu $?
This isn't immediately clear since e.g.:
We often solve  simple charge distributions (like the spherical charge distribution) and use Gauss law with $\epsilon_o$. But technically this charge distribution could have been matter; so if we used $\epsilon_o$ were we implying it was just abstract floating charge? Why didn't we use $\epsilon$ here? Is it omitted for the purposes of teaching basic electromagnetism?
 A: Good and important question, altough one does not 'simply substitute'.
The short answer is that the vacuum values are for microscopic theory of light in vacuum, and any other values are for macroscopic theory, which handles light-matter interaction phenomenologically at much larger scales than atomic separation.
Here is the very long answer:
The $\epsilon_0$ and $\mu_0$ are coefficients in the microscopic Maxwell equations, which describe the fundamental behaviour of light in vacuum. This particular simple and straightforward description of light present for example in the quantum electrodynamics or in quantum chemical calculations (for example time-dependent density functional theory). In the latter, the Maxwell equations sre usually solved with some approximations (instantaneous light, no magnetic field), but the principle is the same.
The 'substitution' of $\mu$ and $\epsilon$ yields so called macroscopic Maxwell equations, which are in principle a phenomenological theory of light-matter interaction at macroscopic scales.
To understand what kind of approximation this is, it is usefull to look the microscopic picture using basic condensed matter theorical desciption of an dielectric, for example, (time-dependent) density functional theory.
In these theories, the electrons of the systems are modelled microscopically accurately. A particular property of an dielectric is that it's internal light-matter interaction changes the response of the system to external electric fields. For example, given an external electric field at particular frequency to a sample, the bound electrons in a dielectric responds to this electric field with partcular amplitude and phase. This 'displacement' of bound charges causes electro-magnetic field of it's own. The electrons (and/or ions) of system further react to this field generating yet another field, and continuing this series to infinity, one can obtain the actual resultant total electro-magnetic field, given a particular external field.
It is notable, that even if the external electric field is of long wave-length, the finest details in oscillations of electrons are of order of 1Å and non-local. These are sometimes referred as local-fields. However, there are charge oscillations also at the wavelength of the electric field, which will yields the characteristic macroscopic effect of dielectric, a non-unity dielectric constant. The non-locality of the description means that electric field at particular location $r$ can induce a field to other location $r'$ via the light-matter interaction. Also, properties of microscopic systems, such as quantum confinement is properly accounted for.
Sometimes, such finely detailed description is inappropriate or unnecessary. One can therefore neglect all local-field and quantum effects, and just phenomenolocically consider the long-wave length part of the total electric field compared to the external electric field. The phase and amplitude differences between long wave-length parts the external and total electric fields are combined into one complex constant, called the dielectric function. If it is imaginary, it means that there is a 90 degree phase difference between the electronic response of the system and the external field is absorped by the electrons. If it is real, it means that the electric field by the electrons either enhance or screens the external field. Usually it is complex, and one has both behaviours. This is the remarkable power of macroscopic Maxwell equations, as they can describe very large scale of phenomena only with one (frequency dependent) complex number. Formally, (or at least as a thought experiment) this can be done by considering the system at larger scale and averaging the microscopic fluctuations.
There are some peculiar features in macroscopic Maxwell equations. For example, in real atomistic surface, the charge density can localize to a finite number of surface layers (~10Å). However, in the Macroscopic maxwell equations, there will be an inifitely sharp surface charge. 
