Dear TCL,
If one does not confuse geodesics with minimal geodesics, then one can say that if you develop the cube onto the plane, then straight lines are geodesics. Of course, not all geodesics arise in this way and I've never considered the question of giving an explicit formula for the distance function.
If $P$ is an $(n-1)$-dimensional polyhedron in an $n$-dimensonal normed space, which we consider as a piecewise flat Finsler space, then a large class of geodesics that do not pass through the $(n-2)$-skeleton of $P$ can be easily described as follows:
(1) On each facet they are straight lines.
(2) They cross the facets transversely and at each crossing they satisfy the generalized Snell-Descartes law (of refraction).
This statement almost obvious because straight lines are geodesics in normed spaces (and hence on the facets, which I consider as pieces of normed spaces with the induce norm) and because the generalized Snell-Descartes law follows from Fermat's principle. I'm a bit short of time now, so I'll edit this answer later to include a description of the Snell-Descartes law in normed spaces.
In the case of the cube with the piecewise flat $\ell_\infty$ metric, this gives that straight lines in the developed cube are geodesics on the cube.