BCE (Before Common Era) and BC (Before Christ) mean the same thing- previous to year 1 CE (Common Era). This is the same as the year AD 1 (Anno Domini); the latter means “in the year of the lord,” often translated as “in the year of our lord.” (It was thought when the AD dating system was created that its year 1 was the year Jesus of Nazareth was born.)
Anno Domini was the first of these to appear. Prior to the 6th century AD, many Christians who didn’t use an Anno Mundi (in the year of the world) type system relied on Roman dating, either marking dates from the year legend had it that Romulus and Remus founded Rome (753 BC) or by relying on the date system established under the Roman emperor Diocletian (244-311), based on the accession of Diocletian.
However, most Christians weren’t too fond of Diocletian, since he brutally persecuted them in the latter part of his reign in the late third / early fourth century. This was supposedly in part a response to advice Diocletian received at the oracle of Apollo at Didyma. Previous to this, he had purportedly only advocated banning Christians from such things as the military and ruling body in hopes that would appease the gods. Afterward, he switched to an escalating policy of persecution to try to get Christians to worship the Roman gods. This began simply via seizing Christian’s property, destroying their homes, burning all Christian texts, etc. When this sort of thing was ineffective, they progressed to arresting and torturing Christians, starting with the leaders. When that didn’t work, Christians began to be killed in various brutal ways including occasionally being torn apart by animals for the amusement of the masses (Damnatio ad bestias).
This method of convincing people to worship the Roman gods ended up being an amazing failure and the persecution appears to have only continued after AD 305 in the Eastern half of the empire under Galerius and Maximinus. Finally, in April of AD 311, by imperial decree, the Great persecution was put to an end even in the East. A few years later, Constantine the Great (reigning from AD 306 to 337) publicly declared himself a Christian and Christianity began to transition into the dominate religion in the Roman Empire.
In any event, Easter was/is the most important holy day of the Christian tradition, and it was decided at the First Council of Nicaea (AD 325) that it should occur each year on the Sunday following the first full moon after the spring equinox. In order to forecast when exactly the holiday fell each year, Easter tables were created.
In AD 525, the monk Dionysius Exiguus of Scythia Minor was working on his table to determine when Easter fell when he decided to eliminate reference to Diocletian by listing his table’s first year as Anno Domini 532, explicitly stating this was referring to the year directly following the last year of the old Diocletian-based table, Anno Diocletiani 247. How Dionysius came up with 525 years since Jesus was born at the time he was calculating his table (532 years from when the table’s dates began) isn’t clear, but he wasn’t far off the range most biblical scholars today think, with the more modern estimates tending to ring in somewhere between 6 to 4 BC for the actual birth of Christ.
The Anno Domini system, sometimes called the Dionysian Era or Christian Era, began to catch on among the clergy in Italy relatively soon after and, though not terribly popular, did spread somewhat among the clergy in other parts of Europe. Most notably, in the 8th century, the English monk Bede (now known as the Venerable Bede) used the dating system in his wildly popular Ecclesiastical History of the English People (AD 731). This is often credited with not only popularizing the calendar reference, but also introducing the concept of BC, notably setting 1 BC to be the year prior to AD 1, ignoring any potential zero year. (This is no surprise as Bede, like Dionysius, didn’t have a numeral zero to work with, see: The Story of Zero. However, they both did at various times reference the Latin nihil, “nothing”, in certain places in calculating their tables where the number zero should have gone had they had such a numeral.)
It should also be noted that Bede didn’t actually use any such “BC” abbreviation, but rather in just one instance mentioned a year based on ante incarnationis dominicae tempus (“before the time of the lord’s incarnation”). While there would be rare sporadic mentions of years “before the time of the lord’s incarnation” from here on out, it wouldn’t be until Werner Rolevinck’s 1474 work Fasciculus Temporum that it would be used repeatedly in a work. The English, “Before Christ” didn’t appear until the latter half of the 17th century and it wouldn’t be until the 19th century that it would be abbreviated.
Shortly after the Ecclesiastical History of the English People, Anno Domini was used officially under the reign of the Holy Roman Emperor Charlemagne (AD 742-814) and in the 11th century, it was adopted for official use by the Roman Catholic Church.
CE and BCE are much more recent inventions. This started in the 17th century, with the advent of the term Vulgar Era; this wasn’t because people considered it to be an age when everyone was coarse or rude, but because “vulgar” more or less meant “ordinary” or “common”, thus reflecting that the era was “of or belonging to the common people” (from the Latin vulgaris).
The first documented instance of the Vulgaris Aerae (Vulgar Era, meaning “Common Era”) being used interchangeably with Anno Domini was featured in Latin works by Johannes Kepler in 1615, 1616, and 1617. The English version of phrase later appeared in 1635 in an English translation of Kepler’s 1615 work. (In the mid-seventeenth century the English “vulgar” took on a new definition of “coarse,” but it wouldn’t be until this “coarse/unrefined” definition would become more common in the 20th century that referring to the Vulgar Era would cease.)
The Latin phrase Aerae Christianae (Christian Era) and the associated English “Christian Era” was also used by some in the 17th century, such as when Robert Sliter employed it in his A Celestiall Glass or Ephemeris for the Year of the Christian Era 1 (1652).
Shortly thereafter, another “CE” came about with Common Era used interchangeably with Vulgar Era, first appearing in the 1708 edition of The History of the Works of the Learned and again in David Gregory’s The Elements of Astronomy (1715).
As for the actual abbreviation, CE (Common Era) has been claimed to have been used as early as 1831, though I couldn’t find specifically in what work it is supposed to have appeared in. Whatever the case, both it and BCE (Before the Common Era) definitely appeared in Rabbi Morris Jacob Raphall’s Post-Biblical History of the Jews in 1856. The use of BCE and CE was particularly popular in the Jewish community where they were keen to avoid using any nomenclature explicitly referring to Christ as “the lord.” Today, BCE and CE instead of BC and AD has become fairly common among other groups for similar reasons.