We derive the general dispersion relation for interfacial waves along a planar viscoelastic boundary that separates two viscoelastic bulk media, including the effect of gravity. Our unified theory contains Rayleigh waves, capillary-gravity-flexural waves, Lucassen waves, bending waves in elastic plates, and the standard dispersion-free sound waves, as limiting cases. To illustrate our results, we consider waves at a viscoelastic interface immersed in water and at an air-water interface. We furthermore investigate waves at a viscoelastic interface separating two identical viscoelastic bulk media, for which we consider both Kelvin-Voigt and Maxwell materials, as applicable to polymer gels and solutions. For all cases, we study how material properties determine the crossovers, scaling, and existence regimes of the various interfacial waves. Since we include viscoelastic effects for all media involved, our theory allows to model waveguiding phenomena in biology, such as pressure pulses in axon membranes, which are possibly relevant for acoustic nerve pulse propagation phenomena.