this is just an update to my previous post because of a recent development. the guys at wikitude released an app called wikitude drive. beside normal features that you would expect from a navigation solution it has an augmented reality mode. in this mode the navigation information is shown as an overlay to the camera view. today they launched it for austria, germany and switzerland. so far it's available on the android market for android 2.1 and above.
it's a paid app so please keep in mind that the refund period in the android market was reduced to 15 minutes.