Examination of Marine Megafauna
The evolution of modern day Cetaceans started from a land ancestor related to today's hoofed animals like cows, pigs and camels. Even though they may appear much like fish, whales and dolphins are all mammals. They are warm-blooded, breath air using lungs, give birth to live offspring and have hair at some stage in their life. For Cetaceans, hairs are usually only seen in the newly born and later disappear as the animals grows.
There are several living mammals today that can give us hints on how an obligate terrestrial animal found itself returning to the ocean. Charles Darwin (1809-1882) described the bear catching prey in the water as an early stage to an aquatic lifestyle. The same goes for the mink and even more so for the otter, which can dive underwater, catch a prey and bring it back up to the surface to eat. Pinnipeds (seals and sea lions) spend part of their time on land but return to the water to hunt. These animals are considered aquatic but not to the same extent as whales and dolphins. Pinnipeds are, for example, still dependent on access to land to give birth. In the evolution of today's cetaceans, a similar transition from an animal living near water to a fully aquatic lifestyle is thought to have occured.
The Archaeocetes:
The early ancestral whales are members of the extinct Archaeocetes. These early whales still had many features that resemble land-living mammals such as differentiation of teeth. Today's whales and dolphins either don't have any real teeth at all (baleen whales) or alternatively, all the teeth have a similar appearance (toothed whales).
The evolution of the whales began around 50 million years ago in the early Eocene. Fossils of an animal called Pakicetus have been found in Pakistan and is thought to be one of the earliest ancestral "whales". Pakicetus had well developed hind-legs. In modern cetaceans the middle-ear is rotated for improved underwater hearing. In pakicetus the middle-ear looks somewhat like something between today's cetaceans and land-living mammals, suggesting an early adaptation to living in water.
Around the same time lived another early relative to the cetaceans who was probably even more adapted to the aquatic environment than Pakicetus. The species is called Ambulocetus natans (fam. Ambulocetidae), which translates to "walking whale that swims". Ambulocetus is thought to have occupied the ecological niche that is today taken over by the crocodiles. An ambush predator that can move both on land and in the water and with jaws large enough to capture and hold large prey.
The first "whales" to be found in South-East Asia have been given the family Remingtoncetidae. These ancestors show new modifications to the ear and earbones, which indicates improved hearing, especially under water.
A few million years younger than Pakicetus we find fossil remains from another early whale. Rodhocetus still had hindlegs although it is suggested that the pelvic bone was no longer attached to the vertebrae. Rodhocetus probably lived entirely in the water and show indications of a tail-fluke used for swimming.
Around 40-36 million years ago during the Eocene epoch lived two other archaeocete mammals: Basilosaurus and Dorodontid. It is disputable whether Basilosaurus was actually an ancestor of cetaceans today but was at least an early relative. The species was first named in 1843 by Dr. Richard Harlan who believed it to be another giant reptile, hence the name Basilosaurus, which means "King Reptile". Although it was a mammal and not a reptile at all, the name wasn't really that bad because Basilosaurus was truly a King with its size. It grew to about 60 ft (20m) and had a long snake-like body shape with a tailfluke. It is likely that undulations of the whole body were used for swimming. Basilosaurids ate fish and sharks. Dorodontid was another long and reptile-like mammal. Dorodontid also had hind-legs with a likely jointed knee and several toes. It is thought that these two species were relatives but NOT direct ancestors to the ceataceans today.
Cetacean evolution
Somewhere between the Oligocene and the early Miocene epochs we have fossil evidence from both toothed whales (Odontocetes) and baleen whales (Mysticetes), (the two large grouping of whales today).
In summary:
The actual evolutionary shift from land living mammals to the first true whales seems to have been fairly rapid, only a few million years. The special adaptations that evolved during this period include a lot of structural modifications to the ears; the bodyshape became slim and perfectly hydrodynamic allowing easy movement in water. This meant everything excessive that increased the drag (friction against the water) had to be reduced including hind-legs, genitals and external ears. along with the hydrodynamic bodyshape developed the tailfluke used for forward propulsion. Although hair is still seen in very young newborn cetaceans it is rarely found in adults. Hair, again, increases drag and slows the animal down thus not beneficial for movment in water. Obviously, cetaceans also evolved a lot of physiological adaptations allowing them to dive and remain under water for prolonged periods of time. Read more about cetaceans adaptations to an underwater existance.