Microcode in its most basic form is just a big look-up table (could be nested if word size is limited) containing the electrical signals for a particular instruction, and a new address to "jump" to (either a subsequent micro-operation, or jump back to the "fetch" micro-op). Electrically, however, there's no difference between a microcoded and hard-wired CPU - they both fetch and execute sequences of instructions.
Of course, there's an obvious advantage to the microcoded approach: your instruction set gets uploaded to your hardware in a ROM! You can change the operation of instructions after the hardware is made, make custom sequences of instructions, or even fix microcode bugs (while uncommon, there have been cases in the past).
I am reminded of the famous Intel Pentium FDIV bug (1994). Seems they had implemented a new and improved floating point division algorithm. It needed only half the cycles of the previous algorithm.
The new algorithm used a 1066-cell lookup table to find partial quotients used in the calculation. Unfortunately, due to a screwup, five of the cells were left blank when the ROM was loaded. This led to obscure errors in the results, which went unnoticed until many thousands of chips were in customers' hands. At that point, Intel had a massively embarrassing recall on their hands.
Example: (core i7, may 2011) http://download.intel.com/design/processor/specupdt/320836.p...
BIOS updates often contain bugfixes for your CPU.
And here's his main site: http://cpuville.com
Remote Host: [<redacted>]
You do not have permission to access this
page or file
Data files must be stored on the same site
they are linked from.
(As noted by krapp, it's a referer check)
Does microcode have to execute like traditional software to be called microcode?
 image of the 6502 at http://www.visual6502.org/images/6502/index.html
 schematic http://www.visual6502.org/wiki/index.php?title=650X_Schemati...
 block diagram http://www.weihenstephan.org/~michaste/pagetable/6502/6502.j...
 details of ROM http://visual6502.org/wiki/index.php?title=6507_Decode_ROM
Is the control logic really random in some way? That sounds impossible. Or at least, very highly inefficient.
Google the expression to learn more.
-- MIPS R4000 Microprocessor User’s Manual, Chapter 1, Page 2
What is the exact interface where a software change leads to a change in some physical word state?
For instance, logically storing X in some register is going to lead to some particular configuration of electrical current on the CPU. I still don't see the exact point where that happens.
How do the two intersect?
This starts with discussion on NAND gates and goes through building CPU components, to a complete computer, to implementing a high-level language for it.
(All the chapters from the book revevant to your question are available as free PDFs).