If your GPS comes with maps, then they are most likely from sourced from one of two companies: Navteq or Tele Atlas. If you use Google Map or MapQuest or Yahoo Maps, their maps are provided by one of those two, as well. The copyright notice tells you which.
In many cases, old maps work just fine, because roads don't change a whole lot. I still use a printed map of British Columbia from 1986, the last time a major highway was added to our road system. Primarily, it's new subdivisions that get added and downtown streets get one-wayed. But sometimes a government starts spending big on roadworks, usually to get reelected, and then serious updates are needed.
I became aware of the flaws in mapping when my financial advisor got lost on a deadend road near our home. The mapping software had told him to go that way, because it incorrectly showed the road went through (and straight up a very steep hill). Researching the problem, I found the were maps provided by Navteq, and that they had other errors: one road in our neighborhood has never existed, another was changed more than 15 years ago. The maps from Tele Atlas don't have those mistakes.
A major highway near us is being four-laned; one road is now cut off and has been rerouted through a tunnel; others are changing to right-turns-only on and off the divided highway. I'll be interested to see how long it takes for Navteq and Tele Atlas to incorporate the changes. Weeks? Months? Years? Ever?
For more about the competition between the two mapping providers, read Wilson Rothman's Map Quest on Wired.com.