It is possible to record your travels via GPS without having a map to show where you are. The device simply records your position periodically as you travel into a "tracklog". In this case, you just need a GPS and software to record the tracklog. The tracklog can usually be displayed on Google Earth after you get back. Google Earth will allow you to "play back" the tracklog which looks like you are flying at a low altitude along your path.
For my Garmin 62s, the City Navigator map for the US, Canada, and Mexico requires nearly 2 GB of storage space. My more detailed 24K Topo covering Washington, Oregon, and California requires 3.75 GB of storage.