Theoretically everyone should see the updated A record somewhere between instantly and the relevant TTL value. Most registrars set the TTL to 24 hours IIRC, so for 24 hours some people will see the old address and some will see the new one and by 24 hours after the change everyone should have the new address, with some instead using a lower value like 4 hours.
If you have access to change the TTL values (i.e. you run you own DNS servers) then you can reduce the TTLs down to something small a day or so before you make your change so the propogation period is much lower.
I say "theoretically" above as there will always be some bugs, glitches, and badly configured caches out there that will mean some users will not see the change for longer. This is especially true if you use very small TTLs as there are still some ISPs out there with DNS caches that ignore TTLs below a given value.
Another thing to look out for is delays between your registrar's DNS control panel and their DNS servers. For instance I noticed that changes made to domains managed by 123-reg.co.uk can take up to an hour to appear on their DNS servers, which is an extra hour on top of the TTL value that you'll have to account for.
Contrary to what Wooble says, the wording is quite sensible. The case that it addresses, of course, is fairly obvious with a little thought: Someone adjusts the name server records to switch from another company's content DNS hosting service to Network Solutions' content DNS hosting service without copying any of the existing other records across, and all of a sudden HTTP and SMTP go awry, as the world at large is no longer told the right places to contact for these services.
Yes, people sometimes do not know that it's necessary to transfer the database across from one publisher to another when one switches publishers.
And contrary to what spacehunt says, things will not soft fail if you switch the servers before copying the database. In the absence of MX resource records, SMTP Relay clients will fall back to A and AAAA resource records, per RFC 2821 § 5. They won't be there, of course, since you haven't copied them over either. The SMTP Relay clients will bounce all queued mail as undeliverable. Soft failures occur in the event that DNS query resolution fails to get an answer at all, not in the event that query resolution succeeds and gives a zero records answer.
In a similar vein, do you know that it isn't necessary to switch DNS hosting companies if all that you want to do (This is what you've told us.) is point HTTP service somewhere else? As you've explained it, what you're doing seems entirely unnecessary. You have company A providing SMTP mail service and content DNS service for the client, and company B providing content HTTP service. To make company B's services known to the world, it's not necessary at all to replace company A with a company C — Network Solutions. Just go to the current content DNS service provider and enter the necessary A and AAAA resource records into the database.
Best Answer
Every DNS resource record is cached; whether the DNS server itself is moving or not is immaterial. As Yahia said, how long the record is cached is determined by the TTL of the record. Before performing a DNS change, it is common practice to lower the TTL from it's regular value (a day or more, typically) down to something really small, like 5 minutes.
Complicating this procedure is the fact that some badly-behaved dns caching resolvers ignore the specified TTL and substitute their own values. (The people running these systems need to die in a fire, and if I ever get elected Grand overlord of The Internet, they will). As such, if it's an important system or one used by people outside your direct control, you would be well advised to setup DNAT rules on the system being migrated away from to redirect traffic that does get sent to the previous IP address to the new one.