Shedinja is supposed to be the old shell of Nincada. But yes, you must evolve it with an empty slot in your party and a POKEBALL like Hex said.
If you read the entries, I'm pretty sure it says that Shedinja is the old discarded shell Nincada when it evolved.
Shedinja's body is based on an insect's shed exoskeleton. Therefore, its body is completely hollow (it possesses no internal organs). The shell consists of chitin and is entirely incapable of movement. As it is the shed shell of a fully developed Ninjask, it has a similar shape to the latter. Shedinja's entire body is brown in color; the abdomen is of a darker shade. There are four protrusions where Ninjask's limbs were growing. What appears to be its eyes are actually slits; perhaps formerly for the Ninjask the shell housed to look through. Shedinja has one pair of what appear to be tattered "wings" on its back, which is actually where the exoskeleton was torn by Ninjask to break free of the shell. Between its "wings" there is a hole, out of which the Ninjask escaped. Each "wing" divides into three smaller pieces. These "wings" actually don't perform any function, as Shedinja's body is immobile and levitates. Two horizontal lines circle its abdomen. A white halo constantly floats above its head.
