I disagree completely with evasion being the key to Ninja and here is why:
Ninjas have two powers, one they come with a surprise first hit with Ninjutsu, and the second is that when they hit, something good happens. The second point is the one people speculating on the value of Ninja are missing. Ninjas attack, and they are of no use when they are not attacking. Ninjas belong in a deck that attacks every single turn, and I don't think Ninjas are really going to have much of a place in a control oriented deck. Ninjas are going to give aggro decks disruption.
Evasion gets you the first hit with Ninjutsu, but then the Ninja is stuck on the table with nothing to do. If all/most of your creatures have evasion, then your opponent just blocks your Ninja. That doesn't work out in the long run. Evasion/Ninja decks need more help, and would need either cards to give the ninja themselves evasion, and I don't think for a minute that legend is enough, or lots of removal/bounce. I think Ninja decks are going to have to devote way too many cards to creatures for this to work.
The real key to NInja I'm thinking is giving your opponent something else to block. The first thing that comes to mind is having a green rush deck with ninja support. You can block the Ninja, or the Blastoderm, your choice. Make them make painful choices about blocking, especially when you have Ninjutsu up your sleeve. Putting out piles and piles of creatures gives the Ninja you have already put out somewhere to hide, and lets them hit with their abilities again more easily. I'm thinking a Ninja deck with 34-40 creatures, with the Ninjas replacing Sorceries and Instants in the deck, and just being a beatdown/disruption deck, with the Ninjas for the disruption. Basking Rootwalla, River Boa, Wild Mongrel, Birds of Paradise for the sole evasion in the deck, Blastoderm and possibly Spiritmonger. Definitely pack Rancor, and don't be shy about putting it on the Ninjas to let the trample damage trigger their abilities.