From this MSNBC site:
Fuchs and his colleagues now have identified three new species of octopuses (Styletoctopus annae, Keuppia hyperbolaris and Keuppia levante) based on five specimens discovered in Cretaceous Period rocks in Lebanon. The specimens, described in the January 2009 issue of the journal Palaeontology, preserve the octopuses' eight arms with traces of muscles and rows of suckers. Even traces of the ink and internal gills are present in some specimens.
image: Dirk Fuchs/LiveScience.com