Check out these entries on how the Greeks did it by /u/400-Rabbits or how the Mesoamericans did it from the FAQ. In the "west," or areas surrounding the Mediterranean and Europe, they largely used their rulers as landmarks. Answering your main question, here is another great FAQ answer by /u/sunagainstgold detailing how our current system came to be thanks to a certain Dionysius Exiguus.

To add onto the above answers, in Republican Rome (and into the Empire as well), dates were almost always given by the names of two consuls (the highest elected position, which was conveniently held for 1 year). In terms of defining bigger eras, saeculum, meant to designate around 100 years, were generally known about and celebrated. We can see both of these dating methods in use by the Imperial historian Tacitus, who in Book 11 of his Annals says

With the same men as consuls, the Secular Games were witnessed in the eight hundredth year after Rome’s founding, the sixty-fourth from when Augustus produced them.

Not all too long after Jesus' time in the late 200s AD, the Roman Emperor Diocletian introduced a dating system based on a census occurring every 15 years, since it was getting unreasonable to use regnal years due to the division of rule of the Roman Empire. Thus "in the 4th year of the census" becomes more common in this era and into late Antiquity.

There are innumerable ways that communities kept time in antiquity since there was much less of a global culture. Even in Rome's own provinces, they often used year numbers from the founding of the province itself. See this chapter of Mathisen's People, Personal Expression, and Social Relations in Late Antiquity for more talk about this particular dating system and Diocletian's, among others, in Rome, as well as a bit more on Exiguus.

As with many things in history, Exiguus' system took placed gradually. It really wasn't in widespread use until around 800 AD, thanks to the fascinating Anglo-Saxon monk Bede who revived it and Charlemagne who adopted the system. This article, which admittedly has a lot of discussion unrelated to your question, gives a good overview and might answer some of your related questions.

I'll leave discussion of the switch from AD/BC to CE/BCE (a much more recent phenomenon) to someone more qualified.

TL;DR: Just about everywhere used their own system of dating for a really long time, usually based around their rulers' reigns. A Gothic monk named Dionysus Exiguus came up with the AD/BC era idea, and it was popularized in Europe when Charlemagne started using it. So while no "decision" was exactly made to switch, Charlemagne's 801 AD decision to adopt it propagated it to Europe and started the trend.

Edit: I wasn't aware of just how common this question was. Here are a bunch more answers.

Also, while Bede isn't super related to this discussion, I can't help but link a great podcast episode in the History of English Podcast about him.