It means that the new DNS 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.) This DNS information does not travel to each of the Internet backbones in a straight line. It travels much like the mapped routes for any given address within the streets, avenues and boulevards included in a map of a country - in a multitude of directions and connecting paths to its states, counties, cities, communities, etc.
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. (Said computers are generally connected to the Internet via an ISP which is another whole topic and has impact on what particular backbone and route your computer will take to a particular Internet location. But I won't get into that aspect of the Internet for now, and not at all if it remains unnecessary to the purpose of this particular article.)
Each backbone must pass the new DNS information to all the other backbones to which it is connected, in order that the connecting backbones can update their mapping and they, in turn, must pass along the new DNS to the backbones connected to them. This process continues until each and every backbone in the Internet has received the new DNS and has re-mapped the route to the domain's new DNS.
Here's an analogy that might help:
Imagine that the Internet, much like a human body, is all connected together by a huge central nervous system. The system transmits signals along its length (backbone and all related connections thereto), through various routes along the way.
The backbone connections in turn take the signal and push it along to sequential connecting points, similar to how a sensation of pain or pleasure travels between the brain and the origination point of the sensation, perhaps the full length of the body all the way to its toes, should you stub a toe.
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. In our analogy, if there's a break in the central nervous system, or an impaired area of the central nervous system of the body, it can slow down or even stop the transmission of the signal to the appropriate area of the body.
The actual time it takes a backbone to update a domain's map location (DNS) depends on various factors, such as where along the central nervous system (route) a backbone is located, as well as whether another prior connecting backbone along the route is functioning properly and is able to timely send along the new mapping to this backbone. (Sometimes backbones go down and there's a major outage which affects a multitude of hosts, ISP's, and millions of sites.) 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.
