The ancestors of cetaceans were small, furry four-legged mammals such as Indohyus and Pakicetus. We know Indohyus spent a lot of time in the water, because:
"Its bones were denser than those of fully terrestrial mammals, which kept the creature from bobbing about in the water, and because the isotopes extracted from its teeth show that it absorbed a lot of oxygen from water."
Next comes Ambulocetus, a very nice transitional between land and water-dwellers. Creationists often claim we lack the crucial pelvic bones for Ambulocetus. Below is the original fossil – with pelvis – and a reconstruction of its full skeleton (from discoverer Hans Thweissen's website), as well as an artist's depiction of what it may have looked like.
Rodhocetus is even more whale-like, and Basilosaurus and Dorudon are very similar to modern whales. The latter two had greatly reduced hindlimbs; "the fifty-foot Dorudon had legs only two feet long." Page 50 has a great image of how these creatures represent a gradual shift in skeletal structure from land mammals to whales. However, as Coyne points out, it's important to realize (and creationists often ignore this) that these animals didn't necessarily form a direct lineage. Because evolution produces a "bushy" pattern of speciation, many of them were merely cousins of the ancestors of modern whales – and that's okay, because we can still learn a great deal from them.
Finally, Coyne answers the question of why whales might have evolved from land mammals.
"One possibility involves the disappearance of the dinosaurs along with their fierce marine cousins, the fish-eating mosasaurs, ichtyosaurs, and plesiosaurs. These creatures would not only have competed with aquatic mammals for food, but probably made a meal of them. With their reptilian competitors extinct, the ancestors of whales may have found an open niche, free from predators and loaded with food. The sea was ripe for invasion. All of its benefits were only a few mutations away."
This explanation makes quite a bit of sense. Since there were still plenty of predators on land, it's only natural that the ability to stay in the water for long periods to escape them would be heavily selected for.
There's also a wide variety of other evidence for cetacean evolution from other fields of study, but that's covered in later chapters of the book.