I have no idea how to start one :c
Well... I don't want to discourage you but this is a long and hard task.
If I were to create a map editing now, I'd first look at following (and logical) needs:
-Generic UO map reading api/class
-Generic UO map memory handling api/class
-Generic UO map writing api/class
-A nice friendly GUI to display the map correctly (like UO Client) and some additions to allow use of tools you will create
-Set of tools to work the map (add/remove statics, land, map generation from bitmap, transitions, area commands, etc...)
-Some tools found on UOFiddler to handle other muls/uops as necessary
Depending on what you create first or what comes to your mind, the process may be a lot different. Then you may look at optimizations or even during the development process.
UltimaXNA is headed to be a custom client, but you can modify to allow map editing
This is what I have in mind now, its just the basic description; once you go deeper you will see exactly what is needed