Yeah, it does have to be faster than the speed of the plane, and I also don't know how much faster. I assume a full aero engineering treatment could get you a real answer, but just looking at the relatively simpler physics version can get a few general rules:
Consider a frame of reference where the airplane is still, and the "airspeed" is the air moving towards/through the airplane at the airspeed (110 kts). Just like we learned in private pilot 101, gravity = lift and thrust = drag to maintain level cruise flight.
In this frame of reference (airplane still, 110 kt "wind" blowing by), the drag is anything that makes the air passing by the plane go slower than 110 kts (form drag in the form of rivets and the like), and/or diverts the air from traveling directly from front-to-back on the plane (induced drag in the form of angle of attack). The thrust is anything that makes the air go faster than 110 kt, ie the prop. So yes, in cruise flight the air behind the prop is definitely moving faster than the true airspeed.
The "dirtier" the plane is, the bigger the difference between airspeed and behind-the-prop speed (more drag means more thrust needed).
The bigger the prop circle area is, the lower the difference between airspeed and behind-the-prop speed (moving more air, don't have to move it as fast for the same thrust).
