Surprisingly, perhaps, we have, however, named many more fossil species than living ones, and our understanding of penguin evolution is rather better than that of most families of flying bird - which tend to have light and fragile bones that don't fossilise well. Unfortunately, as is often the way, it's the earliest and most interesting part of that fossil history that's most obscure, since, being older, these are the fossils least likely to be preserved.
But that doesn't mean we have nothing from that time.
I should perhaps begin, however, by defining the term "penguin". Today, it's obvious what penguins are, since they don't really look like anything else. Taxonomically, penguins are the only members of the penguin family (Spheniscidae), which is itself the only living family in the larger order of penguin-like birds (Sphenisciformes). When it comes to fossil species, though, quite where the Spheniscidae ends and the stem Sphenisciformes begin is a matter of debate... so I'm going to ignore all that and just call them all "penguins".
Under this definition, the first penguins seem to have evolved not long after the non-avian dinosaurs went extinct. Coincidentally, that extinction wiped out the last members of the only previous group of aquatic flightless birds, the Hesperonithes... but they lived in the Northern Hemisphere, and penguins are only found in the Southern one, so they would never have competed with one another anyway.
To unravel the earliest history of penguins, then, we have to turn to fossil sites in the Southern Hemisphere that date to the Paleocene, the epoch that immediately follows the great extinction event. One of the most important such sites lies near Canterbury, in New Zealand, consisting of deposits that would have been laid down in shallow seas at the time. The remains of a number of seabirds have been found at the site, but it's for its fossil penguins that it's best known.
The first penguins to be discovered at the site were unearthed in 1980, but it took another 26 years for them to be formally described and given a name: Waimanu spp., from the Maori word for "waterbird". Two different species of this bird are known, the older being about 61 million years old, and so dating to about 5 million years after the K/Pg extinction. As of today, it remains the oldest known fossil penguin anywhere.
Unfortunately, it's not really a very complete fossil, consisting only of parts of the legs and hips. Those happen to be distinctive in penguins, which is how we know what it is, but it doesn't tell us a lot about the rest of the bird. Since then, however, three more fossil penguins have been recovered from the site. One has a leg bone that's rather similar to that of the original Waimanu specimen, and is only marginally younger (about 59 million years old), with a more complete skeleton. Another is known only from part of its foot, and has not yet been given a name or published description.
The third one, described at the end of last year, is not only the best preserved and most complete fossil penguin of its age, it's the best preserved and most complete bird fossil of any kind from the Paleocene. It now goes by the name of Sequiwaimanu. ("Sequi" means "following", since it was found in what appear to be slightly younger strata than the original, although by how much is unclear).
The paper providing the official description also analyses how this penguin was related to others, including a great many younger fossils from elsewhere. Unfortunately, because there isn't enough of it, the original Waimanu specimen couldn't be included in the analysis, although the authors do conclude that the second, 59 million-year-old, fossil is distant enough from it to be given a new name, Muriwaimanu. It also turns out to be the only fossil in the analysis that is more distant from living penguins than is Sequiwaimanu.
In other words, the new, largely complete, fossil belongs to a very early penguin indeed.
So, what were penguins like so soon after their origin? Well, for one thing, it's quite large, with the skull and beak together measuring 21cm (8 inches) in length. That's partly because the beak is long and spear-like, implying that this shape may be ancestral for penguins, and that the earliest forms therefore probably ate reasonably large fish or squid. Studies of the skulls of some penguins that lived a few million years later also suggest that they did not yet have the visual acuity of the modern sort (although no worse than many living diving birds, such as grebes), perhaps implying a shift in their diet and/or feeding tactics as evolution unfolded.
There are also significant differences in the limbs of these early penguins. The legs were longer and more slender than we'd expect in modern species, indicating that they were likely used in a different way. It could be that they didn't yet "waddle" or walk fully upright (although, if so, they probably got the hang of it not much later), or perhaps they still used their legs to kick themselves forward while swimming, and not just for steering, as modern penguins do. Or both of those things could be true, of course.
Meanwhile, the shape of the bones in the wings suggest that they could be folded up. In other words, they actually were wings, and not flippers. Sure, these penguins were already flightless, since their wings were nowhere near large enough to keep them aloft, but, again, it makes them reminiscent of other diving birds like cormorants, or perhaps the extinct great auk, which was also flightless, but a superb diver.
What even this well-preserved fossil doesn't tell us, however, is where penguins as a whole relate to other kinds of bird. Genetic studies indicate that their closest relatives are the petrels and albatrosses, but they're also very close to cormorants, herons, and storks. One thing we definitely haven't found yet are proto-penguins that could still fly. Such birds must have existed at some point, and likely lived alongside the last of the non-avian dinosaurs.
How did they lose that power of flight? We don't know the full details, but they aren't the only diving birds to have done so. I've already mentioned the even earlier Hesperornithes and the great auk, and there are also the plotopterids, flightless booby-like birds that appeared in the Northern Hemisphere a few million years later than the penguins, and survived until the Miocene.
Even today, there is the flightless cormorant (Phalacrocorax harrisi) of the Galapagos Islands. That likely resembles a plotopterid more than anything else, but it might not be a bad analogy for the first of the flightless penguins, either.
[Picture by Nobu Tamura, from Wikimedia Commons.]
And if, anyone is still wondering: it's 1st April. You get a bird on 1st April. Because I say so.