As an brinicles-and-the-origin-of-life/">article in Technology Review explains, brinicles form because when seawater along the ocean surface freezes to form ice, it exudes a high concentration of salt. That increases the salinity of nearby sea water, which in turn lowers its freezing point, so that it stays liquid even though it's really, really cold. (In a way, this is the opposite of the reverse osmosis process that desalination plants use to turn seawater into drinking water.) Pockets of that brine can get trapped inside the ice pack.
If the sea ice cracks, though, something bizarre can happen to those pockets. The freed brine will leak out and, because it's denser than water, it will sink downward toward the sea floor. On the way down, the super-cold brine will freeze any surrounding water that it comes in contact with. As the water frezes, it forms an icy tube around the brine. Brinicles are incredibly delicate, vulnerable to only the slightest touch. As such, they require relatively calm conditions at sea for them to grow, so they're not all that common.
Oceanographers Paul Dayton and Seelye Martin first observed and described brinicles in the early 1970s, and Martin actually managed to grow simulated brinicles in his Seattle laboratory, according to a 2012 National Geographic article (excerpted here). In 2011, A BBC film crew, which was diving in the waters around Little Razorback Island near Antarctica's Ross Archipelago, actually recorded the formation of a brinicle, which took about five to six hours.