The major decision for software you need to make is whether you want to use a raster editor like Photoshop or the Gimp (a free open source competitor to Photoshop), a vector editor like Illustrator or Inkscape, or a CAD-like program such as Fractal Mapper or Campaign Cartographer. Or you could elect to use a hybrid, like Xara, which has both raster and vector capabilities. Or you could get really complex and use a GIS (geographic information system), but that's more about the data and less about the presentation, so I'd recommend starting with an image editor to start with.
These industrial era maps can be created with any of these software types, although each has its stong points. If you want the map to look aged, then you may be best off with a raster editor, as things like creases and tattered edges are easier to accomplish there. The shaded relief look is also easiest to get from a raster editor. A vector program will give you nice, clean lines that are easy to manipulate, and if you want to make a lot of borders, roads, and the like with the ability to modify line styles and colors at any time, then that's definitely the way to go. The disadvantage is that there are fewer users of vector software, so it can take a little longer to get quality help.
For colors, I'd suggest finding a map you really like the look of and just mimicking that to start with. You can always change them as you go along. For symbols, see if you can find the Adobe Carta font. It has a lot of modern-style map symbols in it, and many of them are also appropriate for an early 20th century map.