This is what's known as "palette swapping," which is the act of taking an image with predefined colors and swapping them out for another set of predefined colors.
A simple (yet not so time-effective) way to do this would be to figure out the RGB of each color in the original sprite you want to swap, and map those to a new colour based on the palette you want. IE:
Code:
//Fragment Shader
rgb = texture2D( gm_BaseTexture, v_vTexturecoord );
if (rgb == rgbOfLightGreen) {
fragColor = newRgbYouWant1; //This would be the lighter colour you want
} else
if (rgb == rgbOfDarkGreen) {
fragColor = newRgbYouWant2; //This would be the darker colour you want
}
And the 'newRgbYouWant' values would be determined based on if you want a red yoshi, blue yoshi, etc...
The method I mention is naive and is more to convey what the idea of palette swapping is meant to do. You probably shouldn't use it. I encourage you to look up palette swapping shaders and techniques.
If I were to do this myself, without googling anything, I'd probably lean towards a LUT (lookup table) which allows you to just use texture for your color swapping, instead of having to manually figure out the RGB of every single colour you're swapping in/out. But again, probably best to see what people have already figured out in the way of palette swapping on the GPU.