Firstly, it is important to realize that the refractive index of a material is not an "inherent" property of the material.
Any dielectric material can have permanent or induced electric dipoles. In linear materials, the density of these electric dipoles (called the polarization density) is proportional to the applied electric field. The refractive index is very simply related to this constant of proportionality. In a non-linear material (which you're referring to as an "electro-optic" material), this density will be proportional to higher powers of the electric field (in the simplest cases). Thus, if one takes the ratio of the polarization density to the electric field, one finds it to be proportional to some powers of the electric field itself. Thus, the refractive index now is not a constant of the material and will depend on the field, among other things.
The physical origin of this effect, therefore, is the manner in which permanent and induced dipoles in an dielectric material respond to an applied field. For a more mathematical treatment, look up http://en.wikipedia.org/wiki/Polarization_density , or a quantum electronics book by Amnon Yariv.