After beating Shiva in the first stage when you get the last hit, press B+Start and hold it. When the continue screen comes up you'll be able to play as Shiva. WARNING: He is weaker than his Streets of Rage 2 character.