I use a bluetooth GPS (Globalsat BT359) paired with my Nokia N800. I use the free Maemo Mapper software, which can download maps from a variety of sources like Google maps, Yahoo maps etc. I've found this to be the best option if I am driving in a car.
I also pair it with my cell phone when I am on a motorcycle or scooter, as the N800 is a bit cumbersome to carry around in my pocket. I then pair it with Google maps. I tried using Nokia maps, but it was quite unusable.