The amount of formality depends on the project, industry, and other circumstances around the project. If I'm operating informally with a client, a simple email acknowledging the change (which often includes an extra cost) will do. If there is no cost change, I will probably even take the direction over the phone. If there is not a good relationshp with the client or I am new to the project, I may ask for a signed form. And if I'm managing a small project, I probably do not need someone to draw up the schedule for me.
There are some projects however that require this formality. Think space shuttle and Boeing and emergency room. These projects must be more exacting as lives are at stake. Every little nut and bolt that is changed when building an aircraft is tracked. Many of these projects are worth millions or billions, and a significant deviation of cost or time may have considerable impact. Many construction projects are subjected to various forms of regulation that require paperwork, so it must be completed.
But it is the responsibility of the project manager to determine the level of formality (and paperwork) required for their project circumstances.