SHEDINJA’s hard body doesn’t move - not even a twitch. In fact, its body appears to be merely a hollow shell. (Ruby)
A most peculiar POKéMON that somehow appears in a POKé BALL when a NINCADA evolves. (FireRed/LeafGreen)
A discarded bug shell that came to life. (Diamond/Pearl)
Shedinja's PokéDex entries have lead many to suspect that when Nincada evolves, it sheds its shell, and that shell can become a Shedinja.If you compare the two Pokémon's designs, you will see that they share head, arm and body shapes, which reinforces the theory.
The most important evidence that Shedinja is Nincada's shell is that Nincada is based partially on a cicada. Cicada larvae shed their exoskeleton when they are ready to fly — similar to how Nincada grows wings when it evolves into Ninjask. The shed shell can then become a Shedinja. The opening in Shedinja's back is in the same place a mature cicada would emerge from its shell; they are even the same colour.
In conclusion, the reason Shedinja can appear is because it is the discarded shell of Nincada. Nincada, similar to the cicada, sheds its shell upon evolution. This shell can become a Shedinja.
A nice video on the cicada narrated by the world's greatest human David Attenborough. Disclaimer, there is some mating but they're insects so it should be fine. I can remove the link if needed.