How do two-leaded color changing LEDs work?

I expect they contain a tiny chip (you can see the little black thing inside) which sequences the patterns. It's either a microcontroller or a special purpose IC.

Most likely something like one of these:

They're available in bare die form and connected to the LEDs inside by ultrasonically welded little wires.

Yes, there is a chip (probably a simple microcontrolleer) inside the LED.