Many questions at once, indeed!
> What is the earliest known true carnivorous plant?  That is, when did
> the first true CP appear on earth?
Possibly as early as Late Cretaceous (or even earlier?), when the 
apparently oldest lineage of recent cps evolved (together with many 
of the older families of dicots), i.e. very roughly 70 E 6 years ago.
> What are the oldest varieties of CPs?
You mean "primitive", i.e. not far from the common origin of all 
dicotyledonous plants? Here I can only make a +/- educated guess but 
it looks like _Nepenthes_ is pretty old and primitive (whereas many 
species in this genus are certainly comparatively young!!).
It derived (as it becomes more and more evident from anatomical and 
molecular examination, and is at least not disproved by palaeontology) 
from a group now clustered around (*not* within!) Caryophyllales. 
This group has been given various names ("extended Caryophyllid 
clade", "Nepenthales s.lat.") none of which sounds really 
satisfactory. It includes (at least) the following families: 
Tamaricaceae, Frankeniaceae, Polygonaceae, Plumbaginaceae (at least 
Plumbaginoideae), Nepenthaceae, Drosophyllaceae, Dioncophyllaceae, 
Ancistrocladaceae, and Droseraceae. You see that a couple of (non-
pitcher-) cps must have followed soon after _Nepenthes_, and some 
apparently "archaic" types like _Drosophyllum_ or _Triphyophyllum_ 
(obviously very old relicts) may even be older than _Nepenthes_. But 
these very early events just cannot be resolved satisfactorily by 
present data.
(Descendants from) sub-carnivorous precursors to the above mentioned 
cps can be found in Plumbaginaceae-Plumbaginoideae. This group could 
be older than the oldest known "real" cp, and a common ancestor 
(i.e. a no longer "missing" link) of as different families as 
Nepenthaceae and Droseraceae. The very pronounced differences in the 
floral anatomy of members of the group demonstrate the long ways these 
families must have gone independently from each other. The more 
surprising is the great extent of homology in gland anatomy (which is 
almost unique in the plant kingdom!) and phytochemistry (no fewer 
than 6 families, including all carnivorous representatives of the 
group contain the naphthoquinone plumbagin in at least one member of 
all genera examined!).
> And what are the newest types of CPs?
Lentibulariaceae are probably of Early Tertiary origin and rather 
certainly the youngest group of cps.
> Are different species of pitcher plants actually derived from a 
> common CP as their ancestor, much like the missing link among 
> humans?
Definitely not. Nepenthaceae (as sketched above), Cephalotaceae 
("Saxifragalean" fragment group incl. Cunoniaceae, excl. 
Saxifragaceae?? Here, a sensible link is apparently missing at the 
moment!), and Sarraceniaceae ("Cornales/Ericales"- group, i.e. the 
most "advanced" pitcher plants) have *very* widely and profoundly 
separated lines of ancestry.
> How were Cephalotus in Australia able to from pitchering habits 
> like Nepenthes, Sarracenia, and
> Darlingtonia...
The _Cephalotus_ pitcher is morphologically not at all homologous to 
any of the other genera of pitcher plants (e.g. the lid is produced 
by the basal transversal zone of a peltate leaf in _Cephalotus_, 
from the leaf apex in Sarraceniaceae, and from an apical transversal 
zone in _Nepenthes_).
Just like with "reptiles" among the vertebrates, "pitcher plants" is 
not a natural (i.e. monophyletic and holophyletic) clade if the other 
dicots are excluded (without this exclusion, the *name* makes little 
sense, however).
>...which were worlds away in distance and environment?   
And morphology (v.s.)!
> Is it possible that Sarracenia and Darlingtonia are related as both 
> are temperate climate growers?
Yes. They are both closely related to each other plus _Heliamphora_ 
(which is also reflected by the fact that they are all placed in the 
same family Sarraceniaceae).
> Both seem to be capable of resisting very
> low temperatures, possibly an adaptation from the retreat of ice age
> glaciation.  Could it be they both had the same beginnings, but were
> separated and isolated when the Rocky Mountains rose and the climate
> changed?
This could be but the exact series of events is not entirely clear.
> Has anyone found any fossilized CPs, such as in coal deposits?
Yes, but most cp fossils are "only" pollen or seeds (mostly from 
Tertiary, belonging to Droseraceae and Nepenthaceae; Obviously, 
_Aldrovanda_ had a comparatively long and diversified history with 
several species even growing sympatrically throughout Eurasia). 
Kind regards
Jan