Don't know about Saturn rockets, but hydrazine and nitrogen tetroxide tanks on Russian spacecraft usually contain what amounts to a nitrogen-filled balloon under pressure. As fuel gets used up, the balloon expands and keeps forcing the fuel against the intake valve; there is no free gas in the tank.

That technique is very common for satellites that use hypergolic propellants (that's almost all of them).

One solution is ullage motors (Wikipedia) to provide artificial gravity.

A more accurate way to say that is that the ullage motors cause a small acceleration that causes the propellants to shift towards the rear of the tanks. The acceleration mimics the effects of gravity but isn't really artifical gravity.

I know that the lower stages of the Saturn were one-time fire stages, but the third stage of the Saturn 5 had to be restarted. How was the engine restarted with the fuel flopping around inside the tank as blobs? I would imagine that unless the unused fuel was forced to the drain opening of the tank, the engine would get a mixture of liquid and gaseous fuel, which would probably be a bad thing.

From this source:

One second after first stage separation, eight solid-fueled motors mounted on the first/second stage adapter ring were fired for four seconds. These provided a combined thrust of 181,000 pounds.

In addition to maintaining the positive motion of the rocket, these motors performed an ullage maneuver, forcing the second stage fuel to the bottom of its tanks in order to feed the engines. The five J-2 second stage engines were fired during this ullage burn.

...

At this point, the Saturn V had achieved a speed of 15,700 m.p.h. and an altitude of 115 miles.

Two solid-fueled ullage motors located 180 degrees apart on the third stage aft skirt were fired for four seconds to settle the liquid fuel. These motors produced 6,800 pounds of thrust.

Three seconds after second stage separation, the S-IVB third stage J-2 engine was ignited. Nine seconds later, the third stage ullage motors which fired at separation and their cases were jettisoned.

The third stage J-2 engine was fired for 142 seconds before being shut down. This initial S-IVB burn was sufficient to carry the Apollo spacecraft into a 118-mile orbit at a speed of 17,500 m.p.h.

At the end of this first S-IVB burn, two ullage motors were fired to settle the remaining fuel and provide spacecraft stabilization. These ullage motors were housed in two Auxiliary Propulsion System (APS) modules located 80 degrees apart on the third stage aft skirt.

Each APS module housed three attitude control motors and one ullage motor. The attitude control motors could each produce 150 pounds of thrust, while the ullage motors could each produce 70 pounds of thrust. All burned nitrogen tetroxide/hydrazine liquid fuel.

During two or three checkout orbits, the S-IVB attitude control motors could be fired in sequence to make any necessary on-orbit corrections. Following these checkout orbits, the ullage motors were fired for 77 seconds to settle the fuel and provide forward spacecraft momentum.