Got it!
Ok, so the basic idea is that on the old days they didn’t had today resources in pretty much any field. So if you want to make a similar look you’ll need to private yourself of a lot of things that today exist.
I happened to be a teenager by the time Super Mario 64 came out, so I was already alive back then, I already was in love by 3D graphics and followed trough closely the jump from 2D to 3D! 
I would say that you mostly start with diffuse colors and then you tile on top a few procedural noise and tile textures. You use them mostly to Bump. but in same cases also to give the diffuse color more randomness!
For example the green wall seems to have:
- A diffuse color shader with correct spectacular and roughness (use the principled shader on Blender);
- A tiles map (for Bump);
- A grunge map (most likely some kind of noise with transparent areas, for extra color and bump);
Fire can be made with particles or an animated painted texture.
Now, back then there wasn’t path tracers, Open GL 3.3, Ambient Occlusion, Bloom or anything like that fancy 
So make sure to don’t rely on the new blender features. Blender 2.01, my first blender would be ideal for this project, but you can emulate it yet today, just have care to don’t over do it.
The rest is the Nintendo guys art direction that defined the size of things (all seems came out from a toy you see), the style and the cuteness Also a very important thing to have in mind.