We have seen several examples of Devil's fruits that have re-emerged after its original owner died. It is known at this point that Devil's fruits don't simply disappear when the owner dies, but rather it shows up somewhere in the world.
Therefore it is not far-fetched of an idea to say that someone or more likely a group of people began categorizing the fruits anytime they came across them. Over the course of hundreds of years, it should be easy enough to compile information such as what they look like, what they do, and other useful information about the various fruits.