By textured shading, I mean the character is shaded with a texture that is filled with a gradient.
You may find some help in opacity masks. Despite Brendan's excellent point about mixing raster and vector art, sometimes it's useful. Sometimes you can get away with a little imperfect scaling, particularly in background textures.
I've used images loaded as opacity masks to bring organic texture to my vector art in the past, such as film or wood grain. Combine that with a blended gradient and you find exactly what you need.
I did a quick search online and found this tutorial - it shows a couple of solutions. You basically need to work in your Appearance palette for layer fills, using transparency effects to get the different fills to interact.
The term "best" doesn't always fly in workflow...while some techniques in some programs are objectively better than others, it's often a matter of preference, resources, application in a specific case, etc.
But one general principle is that when working with vector, you want to use vector-based things as possible. So, something like making a Photoshop texture, placing it in Illustrator, and using that as a texture overlay usually would be less ideal than using a pattern fill, because you're injecting a raster element that won't scale well.