There are libraries available to compute shortest paths on such graphs. How do they do this? More specifically, how do they load the required part of the graph to run Dijkstra's algorithm?
You can use a DB, a custom file format to be read from disc and an in-memory setting.
But from my experience using a DB is roughly 5 to 10 times slower and a lot more memory intense than writing your own file format based on a 'simple' linked list format.
The good thing is there are several software frameworks using OSM which are open source so you can look right into the code e.g. see here. In the GraphHopper open source routing engine it is very easy to switch from a memory mapped setting (disc based) to the in-memory setting - both using the same format. The "mmap" setting even allows usage on memory restricted mobile devices and the latter performs a lot faster if you have the necessary RAM e.g. on a server. E.g. for a world wide graph (>100mio nodes) you then need around 8-10gb RAM, plus lot of more RAM if you want to speed up everything further e.g. with Contraction Hierarchies - roughly 5-8gb more for every vehicle you want.
The format is very simplistic and basically stores only the data you need with a few tricks to make it compact. Read more about it here. Disclaimer: I'm the author of GraphHopper.
Regarding the other answers:
Dijkstras algorithm while applicable is regarded as not optimal for this problem
The 'normal' Dijkstra can perform very reasonable (<1s for country-wide queries like your 3mio nodes example) and is optimal in the 'theory sense' but needs a bit tuning to get fast in production scenarios. And techniques like Contraction Hierachies use a bidirectional modification of it and perform very well.
road networks are hierarchical and planar.
road networks are hierarchical for car only and not planar (bridges, tunnels, ...)