Holy cow, I wrote a book!
If the program doesn't provide this information itself, Add/Remove Programs is forced to guess.
The problem is that there is no "obvious" way to map an entry in the Add/Remove Programs list to an actual program. Each entry in the list, for those who care about such things, comes from the HKEY_LOCAL_MACHINE\Software\Microsoft\Windows\CurrentVersion\Uninstall registry key. The only mandatory properties for an uninstallable program are the DisplayName and the UninstallPath. Everything else is optional.
Let's suppose Add/Remove Programs is given a program registration like this:
DisplayName=REG_SZ:"Awesome Program for Windows"
In order to get the "Last Used" and "Frequency" values, Add/Remove Programs needs to know the name of the EXE so it can ask the Start menu "Hey, how often did the user run this program, and when was the last time it happened?"
Notice that there are no clues in the registration above as to the identity of this EXE file.
So Add/Remove Programs starts guessing. It goes through all the programs on your Start menu and compares their names with the display name of the uninstallable item. It looks for Start menu items which share at least two words with the words in the DisplayName.
For example, if there were a Start menu item called "Pretty Decent Windows Program", this would count as a two-word match ("Windows" and "Program").
It then takes the one with the most matches and decides, "Okay, I guess this is it." Suppose for the sake of illustration that the best match is indeed "Pretty Decent Windows Program.lnk", which is a shortcut to "C:\Program Files\LitWare\Decent Program\Decent.exe". Add/Remove Programs would decide that "Awesome Program for Windows" should get the icon for "Pretty Decent Windows Program.lnk", that the frequency of use and most-recently-used information for "C:\Program Files\LitWare\Decent Program\Decent.exe" will be displayed for "Awesome Program for Windows".
But wait, there's more. There's also the program size. Add/Remove Programs looks in your "Program Files" directory for directories whose names share at least two words in common with the DisplayName. The best match is assumed to be the directory that the program files are installed into. The sizes are added together and reported as the size of "Awesome Program for Windows".
A program can add some properties to its registration to avoid a lot of this guessing. It can set an EstimatedSize property to avoid making Add/Remove Programs guess how big the program is. It can also set a DisplayIcon property to specify which icon to show for the program in the list.
But if a program omits all of these hints, the guess that Add/Remove Programs ends up making can often be ridiculously wide of the mark due to coincidental word matches. In my experience, Spanish suffers particularly badly from this algorithm, due to that language's heavy use of prepositions and articles (which result in a lot of false matches).
Yes, this is all lame, but when you are forced to operate with inadequate information, lame is the best you can do.
[July 15 2004: Emphasizing that this is done only if the program fails to provide the information itself. For some reason, a lot of people who link to this page fail to notice that little detail.]