While still dreaming of a GPS device, I found a number of Linux applications that provide some navigation functionality. The best way to remember URLs is to write them down, so here they go.
TuxMobil links to all these and many other applications for mobile phones, PDAs, notebooks, and the like.