<p>It seems almost magical. What is the traceroute command doing in order to map out the entire path to some other node on the Internet?</p>

traceroute sets the TTL (Time To LIve) field to 1 and increments it for every hop. the routers receiving the message decrement this value and when it reaches 0 they reply a message that the TTL has reached zero. With this reply the client knowns who's in between. do this iteratively until your destination and you got the (at least one of them) route