Eventually, these single-celled organisms learned to group together and cooperate as multicellular animals - the metazoans. Metazoans became abundant around 600 million years ago with the development of a group of organisms collectively called the Vendian Fauna. Fossils of these animals are found throughout the world - most famously in the Ediacara Hills of Australia. Many of these fossils represent organisms similar to those today (like jellyfish) while others represent extinct lineages completely different from anything living in today's oceans.
What we usually teach when discussing the origin and evolution of metazoans in geology class is that single-celled eukaryotes (organisms with a nucleus) like choanoplagellates learned how to clump together and chemically communicate to form sponges - thought to be one of the earliest multicellular organisms.
Sponge classification and their relationship to the rest of the metazoa is problematic (they're not monophyletic for you biology types) but we'll ignore that for now. Problem is that all of the earliest metazoans were soft, squishy things (hard parts hadn't been "invented" yet) and these types of organisms simply don't fossilize well.
There are other, older, weird fossils which have been discovered which may or may not be multicellular. An example is the 2 billion year old Grypania spiralis - possibly a eukaryotic, multicellular, algae.
Most recently, a group of researchers announced in Nature the discovery of 2.1 billion-year-old fossils from sedimentary rocks in Gabon, West Africa that may be metazoans. They've collected over 250 specimens which range in size from 1-12 cm. An example of the detailed x-ray imaging they're doing on these samples is shown below.
The team argues that the complex shape and folding is indicative of more than just a group of colonial prokaryotes, that it indicates chemical signaling - a characteristic of multicellular life. Carbon and sulfur isotopic analysis of the fossils indicates that they are indeed fossils and not simply mineral formations (the soft tissues have been replaced by the mineral pyrite - FeS2 - a common mode of fossilization). Since all the soft tissues are gone, it's a challenge to figure out exactly what these were.
Analysis of the sedimentary rock indicates these organisms - whatever they were - lived in oxygenated sediments some 30-40 meters below the surface of the ocean.
The challenge of talking about the origin of multicellular life is that the fossils are so few and far between and ones we do have provide only limited information. One thing all discoveries indicate, however, is that the story of life on Earth is long, complex, and interesting.