Usually 15 minutes to 4 hours, and up to 24 hours in rare cases. It varies because every network caches DNS records for a different length of time, and you cannot clear a cache that belongs to someone else.
What you can do is lower your domain TTL to 300 seconds a day before you plan to move. The change then takes effect quickly for most visitors.
Check progress with an external DNS lookup tool from several locations rather than your own browser, which caches aggressively and will keep showing the old result long after the change has gone live.
