Domain name "propagation" means that the new DNS information has been communicated to each of the backbones of the Internet and that each backbone has in turn re-mapped its routes to the domain's new DNS location. (DNS = domain name server.)

Each backbone has to re-map the new DNS and pass it along the routes to be taken through it to the new DNS. This routing information is necessary in order for anyone's computer connected to the Internet to traverse the Internet to a particular domain's site.

Within each backbone are various domain hosts. The backbone contains the mapping to those hosts. Without the mapping done by each backbone, no one could travel along Internet routes or view a particular site.

When a Registrar updates your nameservers, your new DNS begins propagating across the Internet. That generally happens fairly quickly (within a 24-48 hour period). 

The actual time it takes to propagate is impacted by how long it is before each backbone receives the new DNS mapping from the prior connecting backbone. Other factors which impact the process are: which week day and time - and its relational traffic patterns, overall Internet traffic, and the actual response time of the backbone itself to update/re-map. (This isn't an all-inclusive list of variables impacting propagation. There are other factors. But you get the general idea.)

How long it takes for a site's new DNS location to propagate across the Internet such that you are able to see a particular site depends on all the above factors and more. Considering the sheer magnitude of the Internet's overall size and the relational requirements involved, it's rather miraculous that it works at all, let alone as rapidly as it normally does.

Here are two ways you can determine if your domain name has propagated:

1. Ping it by going to a DOS prompt and typing: ping yourdomain.com. If your ping returns the new server IP you know it has propagated (at least from your ISP).

2. Do a whois lookup at http://www.nsiregistry.com to make sure the new nameservers are reflected in the whois information.