I've written several posts on similar subjects; they are mentioned below. This is a compilation of sorts.
You only need a piece of paper and pen to start - I'm not getting into "hex maps" for now.
1 - Place the starting point. This is usually a starting village, city, or stronghold. If you're using a piece of paper, make it near the center. You can put it near the edge if there is something in the edge discouraging the PCs from going off map - for example, sea, tall mountains, or "back to civilization" (if the goal is exploring the unknown lands). See the map below - you can use something similar, and start your game anywhere in the East coast (even Florida, near the edge). You can cut it in half keeping only the East coast and Midwest.
2 - Separate land from sea - just draw the outline of your main continent, add some islands if you want.
3 - Add "mountain lines", representing the tallest altitudes. Put a big range of tall mountains to a random direction. Add a smaller mountain range, with hills etc., somewhere else., for variety.
4 - Add rivers. They look like trees with lots of "branches" and trunks on the sea. They run to the sea. They do not cross mountain lines.
5 - Add cities. Most cities are near the water (rivers or seas). In D&D-ish worlds, there are probably few cities and lots of areas inhabited by monsters instead. You do not need to map every village.
6 - Add vegetation. You already have mountains, hills and rivers. Just scatter some big forests, swamps, deserts, plains, etc. I don't usually bother with much realism here. Deserts are usually next to mountains, and vegetation needs water.
7 - Name some regions (no borders needed): "here be goblins" (or "goblin territory"), and do the same for "giants", "dragons", "drow", "slavers", "franks", etc. These "vaguely known" areas can be different human kingdoms, monster territory, or anything else you want to add to you game (e.g, "poisoned swamps", etc.). Use flavorful titles rather than specific names ("Dark forest" rather than "Hullbeck forest"), unless the name is obviously referring to something mythic or historical (Cimmeria, Albion, etc.).
And there you go! You map is ready! Here is my current example (using hextml, but again, you don't need to). Belarte is the starting city. Mektlan is Tamoachan (recommended!). Ilmare is Illmire (recommended!). Savakir is DCC #66.5 (also recommended!). I wrote down "goblin territory" somewhere up north, but it wasn't included in the beginning.
Now, a map is not ALL you need to run a sandbox campaign. So I'll leave you a couple of extra steps that will get you most of the way there.
8 - Detail the starting area. You need some additional detail on the starting area, since the PCs will be more familiar with it. Keep on the Borderlands is a classic campaign starter, but not one I can recommend as I haven't used it. I used BFRPG's BF1 Morgansfort, and I like it - it is FREE! You just have to assign all the relevant locations to somewhere in your map.
9 - Prepare some random tables. It should be obvious by this point that I do NOT encourage you to randomly generate the map, as I've never seems a randomly generated map that looks better than what anyone can do following these simple steps. Besides, mountains can be seen from A HUNDRED MILES away or more; it is absurd to suddenly enter an hex and find a mountain. What you need here is random encounter tables, plus some random tables to add villages, lairs, castles, ruins, and landmarks if you want to do so. I am using this for random encounters, but I still have to find or create some table for locations. I also encourage you to use random events.
10 - Ask PCs where they want to go. They find some random stuff on the way, and when they arrive you should have something prepared. I use classic modules: I use B10 - Night's Dark Terror for "goblin territory" - I really like this one! You can use G1-3 for giants, maybe Desert of Desolation for deserts, etc. Or use the BFRPG versions.
In old school D&D, it is assumed the PCs are searching for gold & glory, so there is enough motive to go around the map. If they need further motivation, you might have to prepare some hooks, backstories, etc.
Additional reading:
