Wired has an article on how map data companies get their information. Assuming sufficiently accurate GPS data from a phone or PDA, they could get real-time data from users themselves.
Maybe everytime a user alerts the system to the status of a road changing, they get 50 cents off their morning coffee. Extra points for new road construction. You'd need a Karma-like reputation system or rely on duplicate reports.