Typically, path maximum transmission unit discovery (PMTUD) happens whenever a host thinks a packet was dropped due to being too large.
This may be in response to ICMP fragmentation required (type 3, code 4) response explicitly indicating the packet was dropped. In typical practice all IPv4 packets are set with the "don't fragment" (DF) flag set, so any packet in excess of the MTU will elicit such a response. IPv6 doesn't support fragmentation at all.
Some routers or host firewalls drop all ICMP often because a naive administrator believes ICMP to be a security risk. Or, some link aggregation schemes may break ICMP delivery. An alternate mechanism to discover the MTU has been exceeded which does not rely on ICMP is proposed in RFC4821.
tracepath is my favorite Linux tool for probing MTU. Here's an example from a host with a 9001 MTU on the LAN, but which must traverse an IPsec VPN to reach 10.33.32.157:
$ tracepath -n 10.33.32.157
1?: [LOCALHOST] pmtu 9001
1: 10.1.22.1 0.122ms pmtu 1500
1: 169.254.3.1 1.343ms pmtu 1422
1: 10.255.254.61 23.790ms
2: no reply
^C [this host won't return an ICMP port unreachable, so tracepath won't terminate]
The ICMP errors can be observed with tcpdump:
$ sudo tcpdump -p -ni eth0 'icmp and icmp[0] == 3 and icmp[1] == 4'
14:46:57.313690 IP 10.1.22.1 > 10.1.22.194: ICMP 10.33.32.157 unreachable - need to frag (mtu 1500), length 36
14:46:57.315080 IP 169.254.3.1 > 10.1.22.194: ICMP 10.33.32.157 unreachable - need to frag (mtu 1422), length 556
MTU discoveries are cached. In Linux this can be observed and flushed with ip (beware of changes since Linux 3.6):
$ ip route get 10.33.32.157
10.33.32.157 via 10.1.22.1 dev eth0 src 10.1.22.194
cache expires 591sec mtu 1422
$ sudo ip route flush cache
$ ip route get 10.33.32.157
10.33.32.157 via 10.1.22.1 dev eth0 src 10.1.22.194
cache
For TCP, exceeding the MTU may be avoided as part of the connection setup. Included in the SYN sent by each end is a maximum segment size (MSS). The TCP header (20 bytes excluding options) and IP header (20 bytes) mean MSS and MTU are related by a difference of 40 bytes.
Here's an example of a connection setup between these two hosts when transferring a large file with scp:
$ sudo tcpdump -p -ni eth0 'host 10.33.32.157 and tcp[13]&2 == 2'
IP 10.1.22.194.45853 > 10.33.32.157.22: Flags [S], seq 634040018, win 26883, options [mss 8961,sackOK,TS val 10952240 ecr 0,nop,wscale 7], length 0
IP 10.33.32.157.22 > 10.1.22.194.45853: Flags [S.], seq 1371736848, ack 634040019, win 26847, options [mss 1379,sackOK,TS val 10824267 ecr 10952240,nop,wscale 7], length 0
In the first packet, the local host proposes an MSS of 8961. This is the configured 9001 MTU, less 40 bytes. The returned SYN/ACK has an MSS of 1379, implying an MTU of 1419. I happen to know in this network the remote host also sent 8961, but the value has been modified by a router since it knows the path includes an internet path (MTU 1500) an overhead from an IPsec tunnel. This router also modified our sent MSS of 8961 to appear as 1419 at the other host. This is called MSS clamping.
So in a sense, PMTUD is happening all the time. In practice, it may actually happen never, if MTU clamping is in place and all traffic is occurring over TCP, or if none of the routers have an MTU smaller than what's configured on the endpoints. Even without MTU clamping it may happen only rarely, when the cache expires.