Based on my own experience (not solving Rubik's cubes, but still), it's similar to how one can navigate with turn-by-turn directions despite not having a map. You just need to know how to "walk the graph" of the objects involved.