Hello!
First, there is a whole section for new and different Fangames, where you could find many useful information and even follow the development of other games.
The program that is used most commonly is, of course, RPG maker XP, coupled with the Pokemon Essential starter kit. From there you can create your maps, add events and other stuff. Most of the core features are already implemented, so you don't have to worry too much about that.
To create the sprites there are some other programs, but I'm not experienced in spriting anyways
But, before you do anything else, you should have planned a good story and some characters. Just try to write down every idea that comes to mind and start from there.
I'll just add that I am in the same boat as you