Hello Maximillian and welcome to the guild. As for software I think try out all of the free ones first and get a general sense of what works for you. For example Gimp paint app and Inkscape vector art app esp on Linux are all free. Krita and a number of other paint apps are free. There is QGIS for a geographical information systems app. Wilbur is an app for eroding landscapes so it will generate random terrain and find the rivers for you. Actually my sig below has a link to a real quick way of generating very rough random shapes as a starting point for worlds. All free. You can use Photoshop or other paid apps have the best features but if your starting then all of the free ones have the all of the features you will need.

If I had to recommend one then try Gimp but its not my personal favorite.

Oh and we have some super maps being done by hand with pen and ink. You dont have to go digital if you dont want to.