It does it by setting the TTL field on the UDP packet it sends out. As packets travel to their destination, every router it passes through decrements the TTL field by 1. Once the TTL gets to 0, the packet is dropped and a destination unreachable message (ICMP type 3) is returned to the sender. This is to prevent networks getting congested by traffic stuck in a routing loop.

Traceroute exploits this by sending UDP packets with customised TTL fields. The first packet it sends has a TTL of 1, the second has a TTL of 2, etc. until it gets the first proper reply from the target. The unreachable messages generated have the IP address of the sender in the packet header, and this is how traceroute determines the addresses of any routers. Latency is determined by timing the wait between the packet being sent, and the unreachable message being returned.

In order for traceroute to be able to do this, it has to have the ability to create raw packets, which is why it's a suid root program. If it didn't have the sticky bit set, it wouldn't work because it won't be able to send any custom packets.