It's surprisingly easy. The ???-Type is rather a pointless type. I did this in three simple steps:
1) Using Tile Molester, I edited the ???-Type graphic.
2) Using a Hex Editor, I repointed the type effectiveness table, so I can add effectiveness for the ???-Type.
3) Using a Hex Editor, edit the text string ???-Type when about to choose an attack (I found this text string and it is obviously three bytes longs, so I can't replace it with "Fairy." I tried to repoint it, but there seems to be no way to? Hmmm.)
**Also, in order to have ???-Type do correct damage, a physical/special split has to be implemented. This has to do with in the normal 3rd gen games, ???-Type is in between "physical" and "special," so with a split implemented, you can properly change the ???-Type to either.