Although I've never really dug into it, I've always assumed mapping out directions in a GPS unit is done with A* or Fibonacci-heaps at a higher level and Dijkstra's algorithm for smaller graphs. Are there any other algorithms being used that aren't immediately obvious?
Stack Overflow has a detailed response to a similar question, I won't try to reproduce it here. For GPS receivers without internet access, likely all major routes are precomputed, and then only supplemented for the end-nodes when heading off freeways. The Google blog has some background on their 'draggable directions', but alas no algorithmic meat.