If I'm going to make a DNS change to an A record for my domain (changing from one IP to another), how long can I expect until people are moved over to the new info? Is it simply <= the TTL? I know it used to take a while, but in 2009 how long should I expect?
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.
For practical purposes, all DNS servers will see a change to an A record somewhere between instantly and the TTL value on the A record. The Wikipedia article has an excellent writeup on this subject.
Individual applications may not see the change within the TTL because of local DNS caches within routers, firewalls, operating systems and applications. As mentioned in the Wikipedia article: "These caches typically use very short caching times — on the order of one minute. Internet Explorer offers a notable exception: recent versions cache DNS records for half an hour"
A reboot (or power cycle for routers) will typically flush all local DNS caches, but obviously you can't expect every user out there to reboot every device after you change your A record.
If you can't change your A records directly, then whatever application makes the changes (control panel software, for example) may introduce its own delays.
We use a default TTL of 4 hours. If we are planning to change an A record, we lower the A record's TTL to 5 minutes (must be done more than 4 hours before the change is to go into place). After the change has been made, we put the TTL back to 4 hours. Most applications see the change right away, but a few users will call in with problems and need to reboot.
The Wikipedia article also has a good discussion on "propagation": "Many people incorrectly refer to a mysterious 48 hour or 72 hour propagation time when you make a DNS change. ...". The root servers (not the registrars) control the TTL on your domain's NS records. You can see these TTL values for yourself with the nslookup command. Right now, the now, the TTL for my NS records on the "F" root server is set to 2 days.
Besides the TTL (something that you control, see Brian Clapper's excellent advice), and possible longer caching times inside some applications, there is also the synchronization time between the authoritative name servers. It can be near zero if every name server receives the NOTIFY and it can be several hours (depending on the settings of the SOA record) if a NOTIFY was missed (something which happens sometimes).
So, to emphasize Brian Clapper's advice: plan in advance.
If you're talking Windows and you're talking internal, it depends on the original TTL. When we knew ahead of time that we were going to make a change, we would set the TTL on the A record low... to 5 minutes. Then once the change was made, we increased the TTL back to a more normal amount.
If you're talking about on the Internet, all bets are off. There are some caching domain controllers that we have seen completely ignore TTL, as already mentioned. In those cases we've gone with a general rule of 48 hours. HOWEVER, if your domain was previously hosted by another provider, and they have not gotten rid of the SOA on your domain, then any of the clients that use their DNS servers will still be pointed wrong. We've seen that issue with BellSouth (now AT&T).
Most clients will work with the TTL that you set. However there are some DNS servers which are configured to ignore the TTL. I recently changed the IP addresses of our web sites. We had to leave servers up and running on the old IP addresses for weeks in order to respond to requests. We finely had to figure out the remaining customers and request that they clean there DNS cache and/or reboot in order to get them off the old IPs.
It could be greater than the TTL of the (replaced) record: Many clients ignore the TTL when its too low, or bound it to some other value (like an hour). There are other caches; Firefox (for example) will cache DNS for a minute (ignoring TTL), but some patches/configurations raise this to an hour.
The sad (but true) answer depends on who's asking for your (DNS) answers.