In this paper, the Maxwell's equations for a tensorial magneto-electric (ME) medium are solved, which is an extension to the work on the uniaxial anisotropic nonmagnetic medium. The coefficients of the dielectric permittivity, magnetic permeability, and of the magneto-electric effect are considered as tensors. The polarization is shown lying in the plane of two perpendicular independent vectors, and the relationship for the transverse polarization is given. The propagation of an electromagnetic wave through a ME medium gives rise to double Jones birefringence. Besides, the condition for an independent phenomenon of D'yakonov surface wave in a magneto-isotropic but with magneto-electric medium is given, which is measurable experimentally when the incident angle is π/4. Lastly, it is shown that the parameter for the magneto-electric effect plays a role in the damping of the wave.