Microcode is essentially a program that runs on the CPU below the level of the normal instruction set (machine code). It's firmware, and stored in some memory on the die (or in the EFI/BIOS, or loaded at or after boot time, depending on the system.) It allows for mapping a large set of complex instructions to short programs of fundamental microinstructions. A CPU without a hardware multiplier might still have an assembly (and machine code) multiply instruction, and simply implement a shift-and-add multiplication algorithm in the microcode.

I suggest Tanenbaum and Austin's "Structured Computer Organization" for a pretty good book about this (and other aspects of CPU design).