I believe these were discovered by a combination of game guides (which receive inside information from the developers) and reverse engineering the code of older games.
The actual Natures was most likely a simple presentation by a paid game guid. The EV's have had some in game evaluator for a while. After that it's all reverse engineering of the code.
You will see in some bulbapedia articles entire algorithms for how Pokemon are caught and for iv's what the internal memory structure looks like, etc. This information can only be obtained by putting the game into a computer card reader, pulling the binary data off the card then converting the opcodes to readable programing code. It is a very complicated process but Pokemon is a very popular game. Also with emulators, cheat devices (like action replay), and other such tools knowing the code behind it becomes well worth the hundreds of hours required to extract and dissect the info.
Here is an open source library you can use to reverse engineer and Recomplie Pokemon red https://github.com/kanzure/pokemon-reverse-engineering-tools
