Typically, messages are numbered by their order on the server. Obviously, this can pose several problems; what happens if there are five messages, and message #3 is deleted? The last two messages' numbers decrement by one! Luckily, the POP3 RFC specifies a method of avoiding numbering issues. Basically, the server assigns an arbitrary and unique string of characters in the range 0x21 to 0x7E to the message. This ID is never reused for any message. When a POP3-compatible email client connects to the server, it can use the UIDL of the messages to determine which messages it has yet to download, which saves time when downloading.
RFC 1725 fully describes the POP3 protocol, including the syntax of the UIDL command, and other related details.
wikipedia.org dumped 2003-03-17 with terodump