The key is that although the devices do no share a common clock, they each have their own similar clocks. Although these clocks are not the same, they have a specified frequency with some tolerance.
When the transmitter sends a message, the receiver uses the preamble to determine the frequency offset between the sender clock and its own clock. The receiver uses this information to perform frequency and phase synchronization, often in the form of a digital PLL.
Sampling at more than one sample per symbol can make synchronization more reliable, although the main advantage to doing this is to perform symbol timing synchronization, so you are usually sampling near the center of the symbol.
I don’t know the specifics of USB2, but most communication channels perform frequency and timing synchronization of some sort, and a preamble gives the receiver a chance to figure out the frequency and timing of the transmitted signal so it can synchronize before the data begins.