As a fellow fangame creator in the making, I'll tell you how I'm tackling my game. May not be the right way, but it's what I'm doing so far.
First, get basic knowledge of your system. I'm using RPG Maker 2003. Own it, look it over, see how it ticks. Understand what sizes of sprites it takes, how the maps work, placements on sprite sheets, stuff like that. Also, I highly recommend using the HELP file if using RPG Maker 2003 (Windows 7 doesn't have help files, just download something from Microsoft that will allow you to. Really. The Help File does help.)
Since you already have story ideas in your head, start making characters. Concept art or directly to sprites. I love making sprites, so I made about 250-350 in a week (though they're mostly just edits from the main twelve walking sprites).
The tedious part for me are the chipsets, also known as the map. Study how the tiles work with each other, how you want your world to look. Dark? Detailed? Cartoony? I try to make it similar to the character sprites so they don't stand out. Also be sure to separate the background from the foreground, have basic land and pathways be the background, things like furniture and doorways in foreground. Special things like the bed that act as events can get their own sprite layer.
I use Paint to make Sprites. A little bit of editing like with color shades on GIMP, a free Photoshop-like program. Sprites are only allowed to be 256 colors on RPG2K3, so save the sheet as .png, open it in Gimp, go to Image > Mode > Indexed Colors (or something similar). Set it to 256 colors. It'll transform it with minimal changes to the actual colors you've chosen.
Now that you have a few sprites down, work in your RPG Maker program. If you've never used one before, it can be complicated. Here's some of my advice:
Look for any tutorial you can find.
Open up Yume Nikki in the maker. Explore the worlds, see how it was made. Unfortunately for me it was difficult to read, but downloading English-based fangames can help. Look at their coding, where they're used, Events, Variables, Switches, stuff like that.
It'll take a bit of practice. And don't copy codes directly. When experimenting it's fine, but no one wants a copypasta. Plus, it takes all the fun out of figuring out the program.
... That was a lot longer than I intended. But I hope it helped.