Legend of Mana is clearly hand painted and then reduced.
The former is often called CG painting (for Computer Graphics), you'll find lots of galleries, communities and Photoshop tutorials about it. For the PC, there are lots of many great free programs you can easily test (off the top of my head : MyPaint, Krita, Art Rage). It's awesome being able to play with watercolors, pastels and oils without having to buy every brush, pot of paint, and canvas !
It's best if you can use a graphic tablet rather than a mouse, because it lets you draw less "heavily" (less opaque, or smaller brush) when you draw slighter strokes. But IMO, you shouldn't overestimate a tablet : It saves a lot of time that you would change pressure / size using a GUI slider, but it's not a magic wand, it won't create something pretty when you're merely doodling at random. The good news is that practicing with a pencil makes you better with a tablet, and practicing with a tablet makes you better with a pencil.
The step of reduction is based on a simple effect/action that all painting programs can execute, but there are ways to improve the end-result : for example if something would be too fuzzy after reduction, you would stress or sharpen it on the source image before you apply the reduction. On the other hand, if an image is intended to be reduced, it shouldn't try to involve details that will be unreadable or misleading after reduction.