In order to explain this we first have to get into details about what the molecules of soda are doing.
In an open container, the amount of kinetic energy of the molecules of a substance determines what phase -liquid, solid, or gas- the substance is in. If the molecules have low energy, they will vibrate in place; this makes the substance a solid. If the molecules gain energy they move faster, and begin to slide around and change places with one another. This energy level creates a liquid. Another increase in energy can make the molecules fly around rapidly, creating a gas. You can see this set of changes by observing ice melt into liquid and then boil to become a gas.
In the case of your soda, quite a lot of carbon dioxide gas was forced into the bottle before it was sealed. When you put the bottle into the freezer you created a supercooled solution; the water in the soda "wanted" to freeze, but the pressure in the bottle prevented it. When you opened the cap, bubbles of carbon dioxide developed as the gas was set free of the pressure. The bubbles created a location for nucleation, which allows the formation of crystals of ice.