Threading predates Gmail by a couple decades. RFC-822 (1982) specifies the necessary fields, and though I don't have personal experience prior to the early 90s

Threading predates Gmail by a couple decades. RFC-822 (1982) specifies the necessary fields, and though I don't have personal experience prior to the early 90s, I'm sure decent MUAs supported threading in the 80s. I actually find Gmail's threading annoying since it only threads at the level of the "conversation" (aka "subject"), even when the initial thread has split. So Gmail doesn't tell me which branch a particular message lives on, and if the reply does not quote enough context, you really can't find out without inspecting the raw message. Furthermore, several messages that should be threaded together, such as a patch series, show up as unrelated messages in the UI because they have different subjects. So Gmail's threading UI does the "wrong" thing because people have a tendency to screw up headers, e.g. trying to start a new thread by replying to an existing one and changing the subject. I'm not sure this is progress.