Take paper and number it 1 through 10 along the long side and 1 through 8 along the shorter. (You can use any other numberings as you feel fit as long as they can both be generated by rolling a single die. When asked to "roll a location", you roll these dice and the coordinates are the location.
One bead's distance is the equivalent of half a day's travel distance (about 10 miles).
Terrain is generated in this order: Coasts, mountains and hills, bodies of water, forest and plains.
Roll a d8 for each edge of the map. On a 1-2 there is a coast there. Connect the coasts as appropriate. This could result in the land being an island (or continent, depending on your scale).
Mountains and hills
First establish you mountain chain(s).
Roll two locations on the map and draw and mountain chain one bead wide from one end to the other. Surround the mountains with 1 bead's width of hills.
After establishing the chain, you can opt to make the region more mountainous by adding more chains of mountains and hills. Add these chains the following way:
Roll a location and place 1 section of hills there (1 sections is about 4 beads square). Roll a d8 eight times, one for each direction around the hills. If you roll a 1, place another section of hills. If you would be placing more hills on hills, change them to mountains. Do this for each section of hills you create and stop when you get no more ones.
Repeat this until you are satisfied with the amount of hills and mountains. Remember that more may be generated at a later time.
Roll a location and place a bead sized lake. Expand it in a similar method to expanding hills. A lake that is determined to be in a mountain is a mountain spring.
Repeat this until you feel there are enough lakes.
This is where it gets tricky. Rivers flow from a source to a mouth. Sources on the map would be mountains and hills, especially if any mountain springs were created. Mouths are coasts and lakes. Make sure that at least each lake has a river flowing into it. Additionally, if you have open borders you can have a river flow off the map if you feel that direction could use some water. Add rivers from sources to mouths, following paths from higher elevations to lower elevations.
For each river mouth, roll a d6. On a 1 that river mouth is either a swamp or marsh (depending on if there are trees there later on). Draw one bead of swampland around where the river meets the mouth.
Plains and forests
To determine if there are any open plains, look and see if there are any large potions of land (4 sections in size) that don't have any terrain marked on them yet. Fo
r each 4 section parcel, roll a d6. On a 1, mark a section of plains in the middle and expand it like with hills. Do not expand into mountains, but hills are okay.
All other open and hilly areas are considered to be forest, but do not mark it as such - it will be disappearing in the next phase.
You may optionally have one or more fantastic features on the map. For each feature roll a location and consult the following chart.
Mountain - Volcano
Hills - Cave Complex
Forest - "Dark" forest
Plains - badlands/desert
Lake - Whirlpool
River - Rapids