What is the earliest sedimentation we know of?
The oldest known metasedimentary rocks are about 3.8 billion years old, formed in the Eoarchaean era.

'Metasedimentary' just means they have been metamorphosed, so they started out as sediments. They are found in the Isua Greenstone Belt of southwestern Greenland. You can read about their discovery in Moorbath (2009). Quoting from there:


  Published zircon dates strongly suggest that the depositional age of at least part of the [Isua supracrustal belt] could be closer to 3.8 Gyr than to 3.7 Gyr.


According to the International Commission on Stratigraphy (Cohen et al. 2013), this puts them firmly in the Eoarchaean era. 

References

Cohen, K, et al. (2013). The ICS International Chronostratigraphic Chart. Episodes Journal of International Geoscience 36 (3). Link to PDF.

Moorbath, S (2009). The discovery of the Earth's oldest rocks. Notes and Records 63 (4). DOI: 10.1098/rsnr.2009.0004