The Black Ship was a large, black Kryptonian spacecraft that arrived on Earth during the 2005 meteor shower. The ship housed the Brain InterActive Construct as well as the Disciples of Zod, Nam-Ek and Aethyr.
In her efforts to expose Lex's secrets a little over two years later, Lana later found out that Lex's scientists have been studying the remnants of The Black Ship. After a year, the ashes began to evolve into its natural form, a black metallic liquid; the liquid was Brainiac trying to reboot. After Lex's lab was destroyed during a battle between Clark and a super-powered Lana, Brainiac escaped (Clark smashed the container he was being kept in, releasing him) and inhabited the body of Casey Brock in an attempt to take humanoid form again.
Without the Black Ship, however, Brainiac had to reboot and repair by absorbing trace metals and large sums of electricity from electric generators and power plants.