warning: tl;dr
Story comes first. Always story.
I mean, think about it. What's the most important thing in a hack? Aside from scripting (which, if you really look at it, is simply a way to put the story into the game), a story is what's going to keep people playing your game. Maps can be poor, and sprites can be ugly, but people will still play it if they enjoy the story. The story is the most important part.
Next, after a basic outline of the story, comes the graphical stuff. I usually like to insert tiles and new graphics and the like to get them out of the way, mostly because I don't like doing them. Besides, it's best to get new tiles in before you do the maps, because you might have different tiles that make mismatches in your maps.
It's around this point that I design a world map. Use your basic storyline as a guide: you don't have to have a name for everything yet. The important part here is that you know what each area is generally like. Like, the general layout; the entrances/exits are most important.
Now you can start mapping. Try to stay somewhat close to your original world map. It definitely won't be the same as you originally intended, but they shouldn't be radically different. I usually map out the first two or three towns and the routes in-between before I move on to the next step.
Scripting. This is, obviously, incredibly important. If you don't have the scripting, you don't have a game. Utilize your basic storyline! Follow it! Be good to your pets! Include humor!
People underestimate how much humor is important, especially in a darker storyline. Of course, sticking to your storyline is your main goal, but keeping the players interested is a very close second. And nothing helps to keep them playing than making them laugh now and then. One particular example I can think of (and not because I've been avidly playing it lately) is Earthbound/Mother 3; you can mix dark storylines with sprinkles of funny. Other games to use for inspiration are the Mario & Luigi Superstar series. Good stuff.
After scripting, you simply rinse and repeat. Go back and map a few places, and then script. If you're feeling tired of mapping, go script. If you're feeling tired of scripting, go map. If you're tired of both, go brainstorm some more ideas for your hack. There's never enough, so write down all of your thoughts. Some of them will be impossible, some of them will seem incredibly stupid, but all of them are important to keep track of. Ideas = important.
After scripting and mapping to the point where you want to stop (say, a beta-ending point), I'd start thinking small. Like, mini. Like, mini-games! [/bad pun]
Anyway, mini-games and side-quests. Think original, think new, think rewards. Doing something original and new is definitely good, so long as it makes sense. And why would anyone do anything if there wasn't a good reason why? Rewarding the player is important. Also, keep these sparse, but common enough that the player will find some. Maybe they'll even try to look for them. ;)
Beta-testing is next. Find reliable people to beta test, not just the random people who ask to do it on your thread. If you are going to allow that, I'd devise a sort of test to see how well they actually beta-test. Create a ROM with intentional errors, as many kinds as you can (tile errors, script malfunctions, grammar errors, anything.) Then, write down all of the problems you've caused in the ROM (at least twenty, to be sure they'll find some). Then you can judge how good their error report was and pick out your beta testers. At least, that's how I'd do it. (Also, make sure it's only a small area that the testers have to go through. Like, maybe a town.)
After the testers go through it, go through it yourself. Don't cheat and give yourself 400 Rare Candies, but play it as everyone else would. Make the really hard parts slightly less hard, and make the easy parts a little harder. A lot of this is guess and check; you'll be playing your hack more than anyone else will. Also, use the wild Pokemon levels. Nothing is more aggravating than a really high-leveled boss trainer (say, level 35 average) but really wimpy wild Pokemon nearby to train on (say, level 14 average).
Once you've made sure everything is perfect (because everything has to be: let no error go free!), release to the public. And as soon as you do that, start working on your next beta. They'll be begging for it soon.
Now, excuse me while I find a thesaurus and look up the word "important". *headdesk*