The answer to your question is ... well, first we have to refine your question:
1) if you're preparing a map you intend to use only as reference for your own writing: I use a blank piece of paper and a fine point pencil. I start with a rough sketch and then fill in details as I need them, moving things around to ensure they make sense geographically as well as story wise. If you're not a student of geography, I recommend finding a few good books on it and studying maps in detail because it's really easy to get things wrong on a map if you're not careful. Also, I recommend the Perry-Castenada Map Library at the University of Texas's web site for a great reference resource. They have maps of all shapes and sizes and ages and links to even more map libraries. Not only is it a great resource for studying maps, it's also a great resource for names of towns, countries, rivers, etc.
2) If you're preparing a map for use in a book:
a) Unless you're self-publishing, your reference map will be sufficient. Unless you're a graphic artist or a cartographer, the publisher will most-likely hire an artist to produce a professional-looking map to be inserted in the book.
b) If you are self-publishing, I still recommend using your reference map as a starting point, but get good inking pens to go over the penciled lines. Once you have everything exactly as you want it, depending on your comfort and computer skills, you could import it into a graphics program to add fine details and the lettering. If you're not comfortable with a graphics program, you may want to hire someone to clean up your map for you. Then again, if you have very clean handwriting, some people love the "homemade" feel of a hand-lettered map - they say it makes it seem like the character drew the map.
I don't recommend using Paint or any basic computer program where you're trying to draw with your mouse unless you're very confident with your skills. I prefer the look of a clean inked map over pixelated maps.
Remember, we're not all J.R.R. Tolkien and making maps is a skill that comes with much weeping and gnashing of teeth . . . I mean, practice.
Of course, file all of this under O for opinion. Others here may have much better suggestions.