First off, I should mention that I have not yet played any of the Naruto games that have been released so far, though I have watched a few trailers for many of them and know a thing or two about the Naruto Ultimate Hero series. I think I have some differences in opinion with those games anyways. Anyways, Naruto is a Shounen Jump series that is all about one-on-one duels between super-powered ninja. It is a natural fit to be turned into a fighting game.
Now then, there is plenty of material inside the series itself to help flesh out the mechanics and movesets of a fighting game. I sometimes wonder if the the author, Masashi Kishimoto, began to intentionally pattern some of the moves of the characters on video game mechanics starting in the middle of the Chunin arc. At the very least, he provided many setting details that help define how a Naruto game can be played.
First off, there is chakra, the energy that fuels all of the special techniques the characters use. Chakra is thus a natural choice to form a special gauge that the characters deplete to perform special moves. The idea of special meter like this is very common in fighting games, such as the Tension meter in Guilty Gear or the Ki meter in the DBZ Budokai series, though its use is often limited to the most powerful kinds of moves. Characters in Naruto can often be seen gathering chakra (often with a certain identifying pose too), so it would make sense to give the characters the ability to charge up the chakra meter by holding down certain buttons.
The kinds of moves that Naruto characters tend to be easily grouped into useful catagories:
1) Regular attacks: The basic punches and kicks that every fighting game character ever seen uses.
2) Ninja weapon attacks: Throwing shuriken and kunai is something that most of the characters in the game would be able to do. Paper bombs, smoke bombs, wires, and giant shuriken also appear. So, there needs to be a mechanic for these kinds of attack.
3) Special attacks: This is where the chakra meter comes in. Every character has an array of special attacks that use chakra to execute. There are big flashy ranged moves like Sasuke's Pheonix Flower, and there are multi-hit combo-attacks that are initiated with a single opening blow such as his Shishirendan. There are also hard to dodge physical attacks such as Lee's Konoha Hurricane. These moves can either seriously weaken or finish off opponents.
4) Special Counters: It is also a common thing for characters to have special defensive or counter attacks, such as Neji's Rotation, Lee's Floating leaf kick, or the Substitution jutsu that just about everyone uses. The flashiest example is Kakashi's ability to mirror his opponent's Special Attacks when they are used on him.
5) Transformations: Between Naruto's Demon Fox forms, Sasuke's curse mark, Rock Lee's 8 Inner Gates, and Choji's special reserve, a significant fraction of the cast shares the ability to change into a super-powered mode where they have way more chakra and power than before. These transformations share some common features that make it easy to design mechanics for them. First off, they give the characters more chakra than normal, which can be emulated by either increasing the size of the chakra meter or letting it regenerate faster than normal. Second, they usually grant more speed and attack power. Third, they are often tiered in sets of two or three. Finally, they all have adverse affects on the bodies of the transformed, which might take the form of slowly draining the life points of the transformed fighter or something similar.
6) Alternate modes: Different than transformations, most characters have special powers that they can turn on or off separately than their transformations. Another Sasuke example is his Sharingan, which would give him passive benefits and open up additional special moves, at the cost of a constant Chakra drain. He also switches the Sharingan on and off independent of his transformation. This also includes other persistent abilities that change a character's fighting style, such as Naruto's shadow clones or Neji's Byakugan. Most would be a constant drain effect that can be turned on or off, or a one time cost effect that can be easily lost.
7) Ultimate attacks: A common thing in Naruto is for a character to have a single attack that is designed to finish off an opponent in a single massive blow, much like Instant Kills from the Guilty Gear games. These include the Rasengan, the Chidori, and Lee's Lotus attacks. They can finish an opponent off instantly if they connect (or at least do some serious damage), tend to power-up and change form when the user transforms, and can only be used a very limited number of times or at some significant risk to the user. However, they also can be easily dodged or countered if used recklessly.
There are a few things that should be mentioned about the nature of combat in Naruto that are both tricky to emulate, but are the most important part of the series' feel. First off, combat takes place in a complex multi-dimensional space. Battles tend to be in huge forests where the fighters are constantly ducking behind cover and moving between layers. The entire cast can walk on vertical surfaces and water. Thus, a traditional flat, one-dimensional space is too limited for the kinds of movement seen in Naruto. At the very least, more complex terrain, like what is seen in Super Smash Bros. or DBZ Tenkaichi Budokai is necessary.
Second, combat in Naruto tends to focus on characters trying to land a small number of powerful blows, where most attacks are dodged or avoided. Even big attacks like the Chidori or Rasengan can be easily stopped by a character catching the arm of the attacker. I never liked the button-mashing/minigame approach to deciding the outcome of this style of attack that is seen in many anime titles, and I think a pervasive dodge/parry system would be more appropriate to the overall feel of Naruto.
The biggest problem with a Naruto based fighting game is that many important members of the cast do not have fully realized movesets. While the developers could try to find things to flesh out the move-lists of these characters with more obscure moves, I think there is a different approach. It might be possible to let the characters have customizable movesets, where you could equip characters with generic moves (such as various elemental jutsu) that some characters can use better than others. While many of the major characters don't have fleshed out move-lists, often their general strengths and weaknesses are known (and sometimes plotted out on handy graphs).
If I ever get around to playing a Naruto game, I plan on critiquing it based on this outline.