There are some excellent documents in the downloads section that can really give you a head start. Personally I would (depending on the idea) start with making a good map with the map editor -which could be interesting to play on. Then I would look out for alternate graphics to suit the style of the game, and start building the scenario via the Cheat Menu (and possibly the Events Menu).
-Also, the RULES.TXT file is the key to editing the scenario rules. The file can be changed with Notepad, as can all the other txt-files. The graphics in the Gif can be changed with an image processor like Paintshop Pro.
From there on, there's a whole world of opportunities! I really recommend you to check out the docs in the downloads section. There are many good articles, also about getting started.
Yours Truly,
Morten