GPS can tell your position. It doesn't need a phone signal for that. But position is just latitude and longitude without a map. To get directions, you need a map. Smartphones don't have on-board maps so need a live data connection to get them. GPS navigation systems, on the other hand, do have on-board maps.

There's no fundamental reason why smartphones couldn't or can't have on-board maps. They certainly have enough memory nowadays, so I wouldn't be surprised if there are already apps that will download maps to your phone's memory.

The iPhone Cyclemeter app will cache the maps over a route if you scroll over that route while you have a data connection. It only caches the map that shows up on the screen at that scale so you won't be able to zoom in or out or wander very far from the course before leaving the map when you don't have a connection.