In practice, it's not the exact timestamp, down to the millisecond--there's a window of 30 seconds or so for each code. On top of that, some services will also accept one of the last (or next) few valid codes too. So it needs to be roughly synchronized, but not impractically so.

Some systems have some extra magic that allow the server to adjust for each device's clock skew; this was particularly important for hardware tokens that didn't have network connections. To imagine how that might work, suppose the server normally accepts responses that are valid at times t-2, t-1, t (the current time, per the server), t+1, and t+2. If a user consistently replies with the t-1 token, we know that her device is running slightly behind and we can instead authenticate against t-3, t-2, t-1, t, t+1.