How do electromagnetic waves travel in a vacuum?

The particles associated with the electromagnetic waves, described by Maxwell's equations, are the photons. Photons are massless gauge bosons, the so called "force-particles" of QED (quantum electrodynamics).

While sound or the waves in water are just fluctuations (or differences) in the densities of the medium (air, solid material, water, ...), the photons are actual particles, i.e. excitations of a quantum field. So the "medium" where photons propagate is just space-time which is still there, even in most abandoned places in the universe.

The analogies you mentioned are still not that bad. Since we cannot visualize the propagation of electromagnetic waves, we have to come up with something we can, which is unsurprisingly another form of a wave, e.g. water or strings.

As PotonicBoom already mentioned, the photon field exists everywhere in space-time. However, only the excitation of the ground state (the vacuum state) is what we mean by the particle called photon.

If we simplify to the classical electromagnetism then the electromagnetic field is a vector field that exists in all of space. A time-dependent electromagnetic field has an electric field part and a magnetic field part associated with it and both are changing with time. They are described by Maxwell's equations.

This website has an nice animated gif which shows how the two vector fields propagates in 3D space. Notice that the electric and magnetic fields oscillate (change values) perpendicular to each other at all times. What we call then radiation is just the travelling disturbance of energy.