Does Electric flux depend upon medium?

The $epsilon$ is defined with polarization and Maxwell's equations in mind such that the equations look as similar as possible to the vacuum case: that is, $epsilon$ incorporates polarization.

Take the first equation, or Gauss' law, like you mentioned. The vacuum-case equation is $$nabla cdot mathbf{E} = frac{rho}{epsilon},$$ where $rho$ is the (free) charge density. In the case of a polarizable medium, there will be bound charges as well as free charges, so we can write $rho = rho_f + rho_b$ (you can infer the subscripts easily). Gauss' law then becomes $$nabla cdot mathbf{E} = frac{rho_b + rho_f}{epsilon_0}.$$

It can be shown that the polarization $mathbf{P}$ is related to the bound charge density as $$nabla cdot mathbf{P} = -rho_f,$$ so, replacing that in Gauss' law and rearranging, we get

$$nabla cdot (epsilon_0mathbf{E} + mathbf{P}) = rho_f.$$

To simplify a bit, consider the case of a 'linear' medium, one where the polarization is directly proportional to the external electric field: $$mathbf{P} = epsilon_0 chi mathbf{E},$$ where $chi$ is a constant called the 'electric susceptibility' of the medium. Inserting that into the previous equation, we get $$nabla cdot epsilon_0 (1+ chi) mathbf{E}= rho_f.$$ We then define the 'electric displacement' or $$mathbf{D} = epsilon_0 (1+ chi )mathbf{E},$$ which is the analog of the electric field in vacuum, with polarization taken into account. Finally, we define the general electric permittivity as $$epsilon = epsilon_0 (1+ chi ),$$ with which, Gauss' law in media looks similar to that in vacuum:

$$nabla cdot mathbf{D} = rho_f implies nabla cdot mathbf{E} = frac{rho_f}{epsilon},$$ since $mathbf{D} = epsilon mathbf{E}.$