Yes it has to be a normal Poké Ball.
Source
Shedinja is considered a "special" evolution of Nincada, appearing only when Nincada evolves into Ninjask, starting at level 20, and there is an extra space in the player's party and the player has an extra Poké Ball.
From Generation IV onwards, a basic Poké Ball (a requirement for evolution) is removed from the bag upon evolution to produce a Shedinja.
Source
Hope I helped :)