Quick FAQ bit: Ephemeris vs. Maps on GPS
Just a quick bit o' nerdy trivia: There are (at least) 3 databases on your GPS that need updating. The big map database is usually copyrighted by a company you've never heard of, and is rarely updated for free. A new map might cost 50% of a new device. Your device-manufacturer may have a special db of [I]corrections[/I], that they give you for free/cheap. Usually, this is what you get when you "update the map." These corrections, in my insignificant opinion, have proven to be of limited use and they have nothing like the scope of the full map. (full map>1gb, typical corrections<1meg or 0.1%)
The 3rd database is the ephemeris, this is free and changes [I]frequently.[/I] This is the guide that tells your navigator where to expect the satellites to be, and it shortens the time-to-first-lock by orders of magnitude, from minutes down to seconds. Besides convenience this db can be the only thing making a lock possible; for example, on power-up deep in a canyon (natural or man-made). This is the part of "updating the map" that I think is really important.
Hope this helps explain some stuff,
tl;dr: the map database is not usually updated for free--map [I]corrections[/I] might be free, but they're of limited value--the db predicting the satellites' position is the real benefit to frequent updates.