The first cells, which evolved about 3.8 billion years ago, needed carbon dioxide to live and not oxygen. They needed the carbon dioxide to help them break down molecules to get energy out of them, and they were able to get the carbon dioxide they needed from the oceans they lived in.
By about two billion years ago, some eukaryote cells had evolved that needed oxygen to live. Oxygen gave them more energy. Mitochondria that could break down oxygen for energy got taken inside other cells to break down oxygen for them.
The first multicellular animals like hydras, about 600 million years ago, lived in the oceans and were only two cells thick, so all of the cells could still get oxygen molecules from the water around them, and get rid of the carbon dioxide molecules the same way.
The first animals that were thicker than that, like earthworms, needed some way to get oxygen to the inside cells that were not in contact with water - a circulatory system. By 420 million years ago, fish developed gills that could take in more oxygen more efficiently, to support a lot of cells that were not in direct contact with the water. Fish also evolved part of their digestive tube into swim bladders, like little balloons inside them that helped them stay at the right depth in the water or go up or come down (like letting air out of a hot air balloon). Mostly these swim bladders were filled with carbon dioxide from the fish's blood. In some kinds of fish, these swim bladders stayed connected to the mouth, so the fish could fill them or empty them faster by breathing in air bubbles. These swim bladders could also work as a backup method of getting air. These may have been the earliest lungs (or lungs may have evolved first).
About 400 million years ago, with a lot of land in one supercontinent called Gondwana, some fish got stuck in smaller ponds that were gradually drying up. Sometimes these ponds were just muddy bottoms with practically no water in them. Some of these fish died out, but some of them evolved to use their lungs for breathing - we call these lungfish.
An iPad2 app to check out how your lungs work
When frogs left the water and began to spend more time on land, about 375 million years ago, they used only their lungs and lost their gills (though baby frogs - tadpoles - still have gills and live in the water). Little by little, frogs also changed their circulatory systems so that the blood with oxygen in it from their lungs went back to their heart and got pumped out again all over their bodies. But frog hearts mix the oxygenated air with non-oxygenated air, so the system isn't very efficient. Frogs help it out by absorbing oxygen through their wet skins too, but that forces them to live near water.
Later reptiles, like dinosaurs, had lungs as well, but by about 310 million years ago they evolved a better double circulation system, where the heart was partly divided in two, to keep the blood with oxygen separate from the blood without oxygen. Now they didn't need to breathe through their skins, so they didn't need to stay near the water anymore.
By about 150 million years ago, birds descended from these reptiles had evolved a complete separation, keeping the blood with oxygen separate from the blood without oxygen. About the same time, mammals that were descended from reptiles did the same thing, but completely separately. This is a more efficient system that allows you to process more oxygen faster, so you can run faster and think better and be more active. Today, all birds and mammals have essentially the same respiratory system. But even people, when they are babies first forming, still show traces of gills.