Nice hack! I have connected a Lassen iQ GPS module to my serial interface. Maps are downloaded from Google Maps servers with a small script. Google maps consist of 128x128 pixel tiles. You have to specify your address, so that map tiles around your area are downloaded. There is also a parameter for number of tiles you want. Zoom levels are possible but require to have a few tile-sets, one for each zoom level. Link.
http://blog.makezine.com/archive/2005/08/gps_for_the_nintendo_ds.html