While I am not a complete expert on traceroute, I can tell you a couple things. Windows operating systems use ICMP to perform the traceroute, and UNIX/LINUX operating systems use UDP to perform traceroutes. Basically packets are sent to the destination starting with a TTL on the IP header set to 1. The first router decrements that TTL, and the packet is discarded. Your host is returned a message from the first router. The host then increments the TTL by 1, and the next-hop router (beyond the first router) is discovered. This process continues until the destination is reached.
While this might not be the best explanation, I am sure there are a bunch of smarty pants engineers that know more about traceroute and can explain it better.
If you really want to learn the nuts and bolts of how traceroute works, download Ethereal
-mike
