Well... There are tutorials out there on the web. I know one has been linked to in this tread before but I can't find it. Even with the search function. I expect someone else here has a link for you but if you don't want to wait, I shall give you some advice now.
Start by recolouring sprites. This will allow you to get a feel for them and how they are done. To recolour sprites use Paint. It is easy to use and works well. Also, it's free!
Here is a quick guide I scratched together. It is not nearly as good as others but it can get you started.
Panel 1: use these two tools to extract and arrange each of the pokemon's colours and arrange them as so. Take all shades from each colour you want to change and line them up in order of darkest to lightest.
Panel 2: chose colours to replace with. Pick colours of the same shade. Avoid yellow for now. It is hard to use. take the colours from the box about midway from the pure colour and grey. It makes the colours more natural on the finished sprite.
Panel 3: use pipette to select you colour to change and the one to change it to as so. Use the right mouse button to select the latter. Select the earser tool.
Panel 4: hold down the right mouse button and drag all over sprite.
Panel 5: repeate with all colours.
Panel 6: make finishing touches if nessary
Please note: that recolour was pretty poor by my standards. I am better than that! I was just in a rush.