Hello all,
Sorry for the delays, but this took quite a while to write, check, adjust, and so forth. Without further ado:

Intro
I consider this to be a basic tutorial, mainly because I'm a novice player-arounder-with-mapping, but I've really enjoyed the results I've gotten from this technique. I've blatantly ripped – ahem, I mean, admiringly learned from and incorporated – techniques found on the forums, especially the one regarding making Not-So-Random-Coastlines, as well as the color palette from the Artistic Regional Map.

About the Tweak Alerts
As I've been writing, I've found places where it might be fun to experiment and do something a little differently than what I've described. I haven't yet tried very many of these "tweaks" and can't guarantee you'll get anything pretty. On the other hand, I can't guarantee something like that even if you do follow my steps, as I'm fairly sure I've mostly been getting lucky up till now.

Stage 0 – Seriously, people
This tutorial is written for use with the current version of Paint.NET, which as of this writing is v. 3.36. Several of the effects I'm using are "plugins" created by users and do not come standard with the basic PDN download. You're certainly welcome to translate this tut to fit your own software, heaven knows I do that all the time, but if you want to use the instructions as written, you kinda need to have the appropriate toys to play with.

Download the following:
Paint.NET v. 3.36 (older versions are not supported and plugins may not work)
Plugins
Threshold
Alpha Mask
Engrave/Emboss
Gradient Mapping
Also, read this thread for instructions on how to install the effects. It's pretty easy.