Story
Ninja Gaiden's story is largely uninspired and quite silly, intentional or not. This time around the Black Spider Clan is attempting to ressurect the "arch fiend" to take over or destroy the world, and only Ryu can stop them. The story is told through a combination of in-game cutscenes and full motion cinematics, and works largely as a little filler to drive Ryu from one slaughterfest to the next.
Gameplay
The first 3D Ninja Gaiden game gained notoriety for the huge move-list and brutal action. In NG2 Ryu has 7 melee weapons available to him, each with one or two level of upgrades and a move-set with dozens of combinations. There are also 4 projectile weapons, including the popular boomerang shuriken, and the return of the ninpo (magic) arts for clearing rooms of enemies.
One of the bigger changes to the game is the introduction of cutting off limbs. From the surface this appears to be a more cosmetic change, but in the higher levels of play and difficulty the severed limbs and accompanying obliteration techniques become very important.
Another significant change comes in the way you can change your weapons and use items. The previous games required you to enter a menu screen and select your items from there, now you can select items just by using the d-pad which is a more streamlined process.