I understand that for magnetic lines of the rotating magnetic field to cut the windings of the rotor (and induce current), the field has to rotate at a slightly higher rate than the rotor. But if we assume the motor starts from zero RPM, at what speed does the field rotate at this moment in time? Do we have to somehow sense the rotating speed of the rotor and adjust the frequency of the 3-phase input voltage somehow? I think this is not what happens, since such a requirement seems somewhat complicated to achieve, especially given that induction motors have been around for quite a long time. So what am I missing?
Induction motors are amazing machines - they utilize several physical principles in a very elegant matter.
Your statement "The field has to rotate at a slightly higher rate than the rotor" is correct, however, there aren't any sensors. The physics is the only thing that makes it happens. Lets deal with the classical case of a three phase motor, without using any variable-frequency drive. The induced magnetic field angular velocity around the stator axis is the same as the power supply frequency. Seek for 3 phase electrical machines or rotating magnetic field in google for more information:
Without naming each phenomena specifically (look for Lenz's law and Lorentz force if you are carious about it), lets try to describe what is going on under the motor's hood: The rotation of the magnetic field exposes the rotor to a time varying magnetic flux, which in turn induces electrical current along the rotor winding. Next, since the winding now conducts electrical current and also subjected to a magnetic field - a force is exerted on the winding, creating a torque around the rotation axis and causing the rotor to accelerate.
This is where the beauty of the motor design really come into play. As the rotor accelerates, its relative angular velocity with respect to the rotating magnetic field is gradually reduced. Is it clear? just to remind you that the magnetic field rotation speed is constant and dependent only on the supplying voltage frequency. As the relative velocity is getting smaller, the induced current also decreases and so is the accelerating torque. For each external load (torque) acting on the rotor, a different constant angular speed would be reached. At that speed the relative velocity between the magnetic field and the rotor will result in an internal torque equals to the external one. This is why an induction motor will never rotate at the exact magnetic field speed (and therefor called asynchronous motor). If it was able to rotate at that speed, the relative velocity would be zero so no torque would be applied on the rotor.