I've decided to take my time out and make a tutorial for recoloring Pokemon sprites and basic MS Paint help. I hope this teaches you something and you appreciate my work:
Step 1: Choosing a PokemonFirst step to making a recolor, is to have the actual sprite at hand. Thanks to the brilliant Polar Koala of the Spriter's Resource website, we have these at hand! Save the image to a folder that you like and open it with MS Paint (right click, open with, MS Paint).
Now, the sprites come in huge packs, so after browsing through the ones that you want, how do you get a certain one out? Choose the dotted box tool off to the side, and select an area around the Pokemon with it (don't bother on getting it perfect, just make sure that your Pokemon sprite is completely in). Make sure that you get the back battle sprite as well, and there is no need for the shiny version, then push ctrl+c to copy the picture. Now, start up another MS Paint (not a new document, but another running program) and push ctrl+v on the document to paste the sprites. With the first MS Paint go back up and get the mini-sprites for your Pokemon. After copying them, turn off the program.
Step 2: Making a new workspaceBack to your second MS Paint Program, post the mini sprites so that they don't run over the battle sprites (enlarge the working space by dragging out the corner if needed). Now any of that unnecessary stuff that was dragged with your pictures must be rid of. So using the eraser tool, or the pencil/paint tool with white selected, go through the whole background that doesn't belong. You should end up with something like the picture above (except I didn't get the mini-sprites until the end).
Step 3: In-depth with the pictureNow click the magnifying glass on the toolbar. Select 8X zoom. Now you can see every single little pixel on the Pokemon. Observe the colors. With this sprite, we are going to just color the skin of the Pokemon, so it is very important to find how much shades of colors the skin currently has (4 shades of blue).
Step 4: The color mixerYou're obviously going to need a wide range of colors now right? The biggest mistake people do is they choose the colors from the bottom of the page. DO NOT CHOOSE THE COLORS FROM THE BOTTOM OF THE PAGE!!! There is no range in them and they look ridiculous. Instead, go up to the colors tab, and choose edit colors. From here go to define custom colors. A huge range of colors huh? Now move the curser into the range of greens (for this project). This is how it should look like:

Now we've got the color, but there is still the same problem, there is not enough range and it would just be stupid to move the curser around every time. So what do we do? Look to the right of this window. There should be a shading bar. Why most recolors look so bad is because they use the colors at the bottom of the toolbar, which are too far away from each other on the shading scale. What you want to do is leave small gaps in between the shaded versions of green.
Step 5: Experimenting with colorsEvery time you choose a shaded green color, push ok and use the pencil tool to make a small square (2 x 2 pixels) that has the color. Go back to the same window and move the shader down and do the same thing, making a square right under the first. After doing this two more times, you should have the 4 shades of green to replace the original 4 shades of blue, in order from lightest to darkest.
Step 6: Lightest to darkestGenerally when using a completely different color scheme, the way to go is replacing the lightest color of the original scheme, with the lightest color of your scheme (with similar color schemes it should be the opposite, with the darkest starting first, or complications may occur). Look above to see the first step. Now with the second color:

The third color:

And the fourth color:

Notice how black was not replaced by anything. UNLESS BLACK WAS USED AS THE COLOR SCHEME, DO NOT REPLACE IT. It is often used as a border, so it is best to leave it as it is.
Step 7: The Final ProductZoom back out to 1X using the magnify glass tool. This should be the progress you made so far. You want to take a break? Then go up to file, and click 'save as'. After choosing your folder, there are many things that you must keep in mind. Look at the bottom of the window where it says 'save as type'. It is important that you save it as a usable type, I personally like to use .png files because they work in any situation:


Anyways, I went back and did all the rest. It is for your use if you want. Be sure to give credit to Polar Koala from Spriter's Resource for the rip, and please don't claim it as your own (even though now you should be able to make one of your own.

).