If I want to design a fictional map, not taken from real world DEM, I prefer to use something like World Machine. It is a sophisticated node based terrain design tool. It makes it easy to add natural effects such as erosion, coast lines, cliffs, ridges etc.
If you have a 3D sculpting tool, such as Zbrush, Sculptris, 3D Coat, or some 3D app with sculpting options, that's also a way to make your landscape. Just keep in mind you need to export the geometry from top down as a greyscale image map. There are different ways of achieving this depending on the software.
In all simpleness you can make a document in Gimp or Photoshop and paint a greyscale image in values from black to white. Black is the lowest point, white is the highest.