Traceroute, ICMP, UDP and TCP

ICMP messages are still IP packets. Traceroute uses ECHO Request (ICMP type 8) by default on Unix and Windows with incrementing TTLs, logging the sending address of each Time Exceeded (Type 11) message it gets back from the hops along the route. (cf: http://en.wikipedia.org/wiki/Internet_Control_Message_Protocol)

This is the 'correct' way to do it, but you can run in to problems if some of the systems on the route drop or differently handle ICMP traffic.

Some implementations of traceroute (on Linux for example) have -T and -U options for switching to TCP/UDP instead (and a following -p argument to specify a destination port). This is useful for more closely simulating real traffic, which might get you a more accurate result in some cases.

I suspect the OSX implementation defaults to UDP for that reason, but I can't say for sure. You might find a switch to use ICMP instead.

Windows Tracert typically uses ICMP with a specific TTL. The TTL is increased each hop until it reaches the destination. This means the first hop has a TTL (max-hop-count) of 1. Even though the packet doesn't reach the target, the first hop drops it and sends a TIME EXCEEDED message back, this message is used to map the route, and the next ICMP is sent with a TTL of 2.

OSX and Linux use UDP by default with increasing port numbers, but both can be configured to use TCP, UDP, ICMP, or GRE packets.