Here are 5 pictures to help you get going on sorting it all out. You have layers in GIMP (I hope you are using this). Use layers to the max. As this is your first map, have a layer for everything. From small dots to large swaths of colour.
This first one will give you a colour palette to work from. All I did was use the gradient tool with the same colour (dark and light). Find a set of colours you like this way and stick to them. As you are going for a historical map, it would be nice to see them from the left side of this. Some different shades can be used like for water but a good rule is to see if you can stay in one area of the palette.
![Image](http://img839.imageshack.us/img839/8940/48606287.jpg)
In this second one, all I did was lower the opacity of the colour layer. It brings out the layer below but it changes the colours as you have now added the colour from the layer below. Do not worry, colours can be changed later. But the big benefit of this is it allows the texture from the layer below to show through.
![Image](http://img23.imageshack.us/img23/8655/69513980.jpg)
Now this is where things can get interesting, but give great results for a little work. Duplicate the layer with the colour on. You can do this by clicking on the layer so a box pops up. On the duplicated layer, add some noise (I see you have done this). Now go to filters and find emboss under distort. You will get a box with slides in. By moving these around you can get some bumps and valleys of varying light/darkness. It will be in black and white. The next two pics show you the difference between the layer opacity.
![Image](http://img145.imageshack.us/img145/8339/48257638.jpg)
![Image](http://img404.imageshack.us/img404/1124/61415253.jpg)
Lastly, this is the background paper I used. It is the same paper I used in the Alternative history map.
![Image](http://img443.imageshack.us/img443/4138/84139166.jpg)
Now for lines.
When you do you lines, thicker ones use the Circle Fuzzy (03) (5+5) at 100% size. For thinner lines like borders between territories go for the same brush but set it at around 85%. You can change the size of the brush in the paint brush tab under scale. Make sure you use the paint brush at all times. Later, we can go through ink and what not but for now, use this.
GH, I know this is a lot of info for you but the only way to get better is to go ahead and do it. Practise makes for a better map. Keep posting and I will help. I will leave it to you and tk for the historical parts of the map.
![Wink ;)](./images/smilies/icon_e_wink.gif)