Place the potatoes in a large pot with enough cold water to cover. Bring the water to a boil and cook, partially covered, until the potatoes are easily pierced with a skewer but the skins are not split, about 35 minutes. (Alternatively, the potatoes can be baked in a preheated 400°F oven until tender, about 40 minutes.)
Drain the potatoes and let them stand just until cool enough to handle. (The hotter the potatoes are when they are peeled and riced, the lighter the gnocchi will be.) Working quickly and protecting the hand that holds the potatoes with a folded kitchen towel or oven mitt, scrape the skin from the potato with a paring knife. Press the peeled potatoes through a potato ricer. Alternatively, the potatoes can be passed through a food mill fitted with the fine disc, but a ricer makes fluffier potatoes and therefore lighter gnocchi. Spread the riced potatoes into a thin, even layer on the work surface, without pressing them or compacting them. Let them cool completely.
In a small bowl, beat the egg, salt, pepper, and nutmeg together. Gather the cold potatoes into a mound and form a well in the center. Pour the egg mixture into the well. Knead the potato and egg mixtures together with both hands, gradually adding the grated cheese and enough of the flour, about 1 1/2 cups, to form a smooth but slightly sticky dough. It should take no longer than 3 minutes to work the flour into the potato mixture; remember, the longer the dough is kneaded, the more flour it will require and the heavier it will become. As you knead the dough, it will stick to your hands and to the work surface: Repeatedly rub this rough dough from your hands and scrape it with a knife or dough scraper from the work surface back into the dough as you knead.
Wash and dry your hands. Dust the dough, your hands, and the work surface lightly with some of the remaining flour. Cut the dough into six equal pieces and set off to one side of the work surface. Place one piece of dough in front of you and pat it into a rough oblong. Using both hands, in a smooth back-and-forth motion and exerting light downward pressure, roll the dough into a rope 1/2 inch thick, flouring the dough if necessary as you roll to keep it from sticking. (When you first begin making gnocchi, until your hands get the feel of the dough, you may find it easier to cut each piece of dough in half to roll it.)
Slice the ropes into 1/2-inch-thick rounds. Sprinkle the rounds lightly with flour and roll each piece quickly between your palms into a rough ball, flouring the dough and your hands as needed to prevent sticking. Hold the tines of a fork at a 45-degree angle to the table with the concave part facing up. Dip the tip of your thumb in flour. Take one ball of dough and with the tip of your thumb, press the dough lightly against the tines of the fork as you roll it downward toward the tips of the tines. As the dough wraps around the tip of your thumb, it will form into a dumpling with a deep indentation on one side and a ridged surface on the other. Set on a baking sheet lined with a floured kitchen towel and continue forming gnocchi from the remaining dough balls. Repeat the whole process with the remaining pieces of dough. At this point the gnocchi must be cooked immediately or frozen.
To cook gnocchi: Bring six quarts of salted water to a vigorous boil in a large pot over high heat. Drop about half the gnocchi into the boiling water a few at a time, stirring gently and continuously with a wooden spoon. Cook the gnocchi, stirring gently, until tender, about 1 minute after they rise to the surface. (You can cook the gnocchi all at once in two separate pots of boiling water. If you make a double batch of gnocchi, I strongly recommend cooking them in batches in two pots of water.)
Remove the gnocchi from the water with a slotted spoon of skimmer, draining them well, and transfer to a wide saucepan with some of the sauce to be used. Cook the remaining gnocchi, if necessary. When all the gnocchi are cooked, proceed according to the directions for saucing and serving in each recipe.