The earliest life must have been something like a small single celled organism, like a bacterium. Or at least, the earliest life that we can usefully conceive of, and potentially connect with living life. It has been suggested that life could have initially evolved at the site of submarine hydrothermal vents, which is a place these days teeming with life. So, it make sense to look for fossils of these early life forms in rocks formed at hydrothermal vents, but a long time ago.
The Nuvvuagittuq belt in Quebec is a geological formation that includes such rock.
There are two basic ways to identify a tiny bacteria like life form. Well, sort of three. Method 1 is to find a physical structure that looks like the life form. So, little bacteria shaped do-dads might be bacteria fossils. Method 1a would be to find that, method 1b would be to find something slightly less direct, such as stramotlites, which is a kind of rock formed from the accumulation of bacteria byproducts. Method 2 is to look at the isotopes of key elements, usually carbon. There are a lot of ways for carbon to get mixed up in a rock. But, the non-life connected sequence of events that put carbon in a rock would sample the ambient carbon in a characteristic way. Since carbon comes in more than one stable isotope, the stable isotope ratio of the carbon in the abiogenic rock would reflect this pattern. But living systems tend to use carbon in a different way. The carbon atoms that get used by the tiny molecular processes involved in assembling molecules are biased in which carbon isotope they end up using. This results in a carbon isotope profile different than the expected ambient one, and suggests life.
Today in Nature, a paper by Matthew S. Dodd, Dominic Papineau, Tor Grenne, John F. Slack, Martin Rittner, Franco Pirajno, Jonathan O’Neil, and Crispin T. S. Little entitled "Evidence for early life in Earth’s oldest hydrothermal vent precipitates" (Nature 543, 60-64) reports, from the abstract:
... we describe putative fossilized microorganisms that are at least 3,770 million and possibly 4,280 million years old in ferruginous sedimentary rocks, interpreted as seafloor-hydrothermal vent-related precipitates, from the Nuvvuagittuq belt in Quebec, Canada. These structures occur as micrometre-scale haematite tubes and filaments with morphologies and mineral assemblages similar to those of filamentous microorganisms from modern hydrothermal vent precipitates and analogous microfossils in younger rocks. The Nuvvuagittuq rocks contain isotopically light carbon in carbonate and carbonaceous material, which occurs as graphitic inclusions in diagenetic carbonate rosettes, apatite blades intergrown among carbonate rosettes and magnetite–haematite granules, and is associated with carbonate in direct contact with the putative microfossils. Collectively, these observations are consistent with an oxidized biomass and provide evidence for biological activity in submarine-hydrothermal environments more than 3,770 million years ago.
I used to work down the hall from a guy who was involved in the search for early life. I won't mention names, but at the time, I remember the fighting among scientists about whether or not this or that piece of evidence was legit was pretty intense. I think things have calmed down a bit. Back then, the battle was between Australia and Greenland. These days, apparently, Canada is in the act.
At present, the oldest evidence of life that is widely accepted is probably close to about 3.0 mya, with several older sites in contention. The newest find, as noted, dates to between 3.77 and 4.28 billion, and I understand the dates are somewhat controversial. If this site ends up as representing early life, it may well be the earliest, assuming the date is anywhere in this range. There are other cases that are close to 3.8 billion but the current study's argument may be stronger. Over the last few years, the very nature of the study of early life on earth has gained a significant amount of perspective and methodological philosophy which I think will allow future work to be considered more sensibly. By this, I mean, that rather than asserting that this or that evidence is certainly indicative of early life vs. not conclusive (or not evidence of life) we will start seeing a more unified characterization of early environments and conditions, along side a better set of models for how life could originate. In that context we may never have an "earliest life" fossil, but we may have a much better story to tell about how early life could start.
I'll add this: Consider the number of scientists working on a problem like aging in muscles, or how to attack a certain kind of cancer. Tens of thousands. Now, consider the number of scientists dedicated to working on the origin of life. Not many. Given the magnitude and difficulty of the problem -- in the field, in the lab, and in the theories -- there is no wonder it is taking science many decades to nail this problem down.
And, no, the origin of life is NOT different from evolution, no matter what the creationists tell you.