This site contains text descriptions of spoof magic cards, but doesn't even have any photoshopped images of them.
It started in 1994.
http://www.frivolity.com
It seems that spoofs of magic cards, and even physically real counterfeit cards were a part of the Magic: The Gathering fandom already only a year after its release. I don't know that we'll ever find THE FIRST EXAMPLE of this, as it likely occurred in multiple places simultaneously.
So far it looks to go like this:
Early text descriptions of spoof cards in 1994
There may have been some early photoshops between 1994-2000 but I have yet to find any.
Most search results that return images seem to come from 2001.