The obvious answer is with some sort of rotary cutter--a router, a Dremel or a CNC mill. And you probably imagine that prior to the invention of those machines, someone had to painstakingly carve these cavities out manually, using a sharp gouge.
In actuality, craftsmen in Sheffield, England were producing perfect-fit inlays like this at least as far back as the early 1800s without carving at all. Instead they used a very ingenious, purpose-built tool called a two-legged passer, parser, parsey or parsa, depending on who's telling the story.
This tool features a forked piece of metal with some funny business going on at the cutting end. Here we see the chisel-like tips and an odd notch cut into each tine.
The tool wielder then puts on what they call a breastplate, though it's really worn on the abdomen. This breastplate has a short section of tubing to accept the point of the iron protruding from the bobbin.
In this modern-day version we can see a bearing has been inserted into the tubing.
A strip of leather attached to a stick on both ends, forming a sort of bow, has been wrapped around the bobbin. The mass of the user's body provides the bearing force of the blade on the material, and the bow is rapidly drawn back and forth, causing the tool to spin.
The rotary motion causes the blades to begin hogging out material. Because the blade is forked, i.e. sprung, the blades can compress inwards to follow the narrower portions of the template. The springiness of the blades is such that they always want to press outwards, which ensures they cut snugly against the perimeter of the template and can even get into corners. The notches in the blades serve as depth stops, hitting the outer face of the template to avoid going too far into the workpiece.