The phase changes here just involve solids and gases, either deposition (changing from gas directly to a solid) or sublimation (changing from a solid directly into a gas). The actual substances in the video are common, just dry ice (solid carbon dioxide) and water frost, the reason no liquids are involved comes down to the temperature and pressure. At normal atmospheric pressure dry ice does not melt, liquid carbon dioxide is not stable, so it changes directly into a gas. Dry ice is also very cold (-78°C/-108°F) meaning water vapour (a gas) in the air coming into contact with the dry ice directly deposits to form frost. In some places it also hits the cold carbon dioxide gas and solidifies from the air to form tiny snow particles.
The frost looks black and the dry ice looks white because of the way the sample was illuminated. It was lit up from the back and frost (which has lots of tiny crystals) scatters the light away from the lens, making it darker. Dry ice scattered the light less, i.e. light got transmitted straight through to the lens, so appeared lighter.
Over time the carbon dioxide gradually sublimates and the water frost gradually forms. Because the surface the frost is trying to grow on is constantly disappearing the frost constantly moves. As the carbon dioxide sublimates it also increases greatly in volume, blowing the frost about!
This video is of a microscopically small sample. The region the video shows is only about 1mm across, depending on the size of your screen you are seeing the frost and dry ice at 100× to 1000× its actual size. This high magnification lets us see individual ice crystals growing as the frost spreads. Initially the crystals in the frost are very small (5μm or so). Gradually as the dry ice sublimates the temperature increases and the water vapour in the air can take longer to deposit onto the growing ice crystals. Slower crystal growth leads to bigger crystals (up to 100μm).
Ice crystal shapes also vary depending on temperature and environment, in this video you can see both needle-shaped and flat ice crystals.
The frost grows and the dry ice sublimates quite quickly. All the clips in the video are at 4× real life, if you imagine everything happening at a quarter of the speed that is how fast the frost was growing and changing.
ImageJ: Image editing, alignment, cropping and video making,
Audacity: Audio editing.
Windows Live Movie Maker: Final sequencing, adding captions.