That's a very interesting question, but one I have to admit I am not capable of answering in the exact sense that it was meant (for I fear we lack the sources), but I'll have a few observations that might make it easier to understand why they didn't have to.

First off, I find it highly unlikely that people would have the complete sequence memorized, at least I don't know of any example where this is mentioned, I might be wrong though and I'd be happy if someone could correct me on this. There'd be roughly a thousand pairs by the time we reach the later imperial times.

We also know that the Romans referred to the dating by consuls quite often both in literature and in letters, for example Cicero in his letters to Atticus dates events by the consuls, Livius and Tacitus use dating by consuls extensively in their histories, as do other authors, so there must have been an expectation that their readers would have understood them and know which temporal period they were referring to - or the other way around, could in this way connect the consulship of a pair with specific historic occurences. Of course their audience is the elite, but for the lower strata our sources on how they perceived time are even less vocal.

In that sense, a Roman would have known that Caesar was assassinated in the year of his 5th consulship. So certain consulships are associated with important, well-known historical events and vice versa. Cicero, when writing in Brutus [287] about a certain vintage of the famous Falernian wine, refers to it by being from the consulship of Opimius (120 B.C.) or Anicius (160 B.C.):

... so excessively old as to date its age from the consulship of Opimius or Anicius...

That's 100 years in the past at the point of time where Cicero is writing. So many consulships as relative fix points in time one could orient oneself from would be well known. Say if I told you that I was born when Reagan was president for the second time, you'd probably know roughly when I was born.

What I mean with that is that to give some meaning to arbitrary references to points in time, we have to link them to known fix-points in time. '1987' is just a sequence of numbers, even if the sequence of years from 1-1987 is easier to memorize than the sequence of consuls from 753 BC to 541 AD.

But how would you go about making sense of such a reference in Roman times? If consular dating is so important, and people can not necessarily be expected to memorize the whole sequence, this information would have to be made publicly accessible without having to consult a history book or library.

You accidentally did pick a rather famous pair, since Popilius Laenas and Aelius Ligus were the first pair of plebeian consuls of the Republic, so that would be rather remarkable for people interested in politics. In any case, it is an instructive example, because we can see a few things here. I know, you said substitute for less prominent ones, but bear with me.

The solution to this problem lies in the so-called fasti. Some of these fasti recorded the calendar year, the important dates during the year, the market days, which days were auspicious for the transaction of public business and so on. But other lists existed that enumerated all the consuls. The most famous surviving example are the fasti capitolini (named thus because it is kept in the Musei Capitolini at Rome), probably originally carved into an arch on the forum commemorating Augustus' victory at Actium. It is only preserved in fragments, but what it is is a long list of consuls (and also f.e. dictators).

To get back to your example, you could look up Popillius Laenas and Aelius Ligus on there to see both where they fit in the relative chronology (compared to those who came before and after them), but importantly also in how they fit into absolute chronology.

Here's the relevant part, fourth line from the top.

Two important things to note here. First, at the beginning of the line, you'll see 'DXXC' - every tenth year was marked thus, these are the years according to the Varronean era, so the 580th year from the founding of the city (172 BC) for the year before. Second, below their two names - here given as C(aius) Popillius P(ubli) f(ilius) P(ubli) nepos Laenas, P(ublius) Ailius (=Aelius) P(ubli) f(ilius) P(ubli) n(epos) Ligus - you'll see two more lines: Ambo primi de plebe, 'first (consuls) both from among the plebeians', and second bellum persicum, referring to the third Roman-Macedonian war which began in 171 BC - or in the consulship of Popillius Laenas and Aelius Ligus.

So the relative chronology is here explicitly linked to a different measurement of time that makes comparison easier (nb the measurement AVC had only been established a short while before), and to a fixed point in time, the third war with the Macedonians. This is just an example from Rome. Other fasti existed in many other towns. Another prominent one would be that from Ostia, which is a bit more verbose in linking consulships to the memorable events that happened. They preserve the timeframe from 49 B.C. to 175 A.D., and begin thus:

Pompeiu[s urbem reliquit] / [i]nterregnum / [C(aius)] Caesar [P(ublius) Servilius] / Pompeius Al[exandriae occisus]

'Pompeius has left the city / interregnum / (next year) Caius Caesar, Publius Servilius (were consuls) / Pompeius was killed at Alexandria'

In this fashion, every year is linked with important events. This need to establish fix-points in time was also recognized by Polybius, who in the beginning of his history (I. 5-6) fixes his starting point as the sack of Rome by the Gauls and relates it to other important events his readers would know about (worth quoting in full here I think):

I shall adopt as the starting-point of this book the first occasion on which the Romans crossed the sea from Italy. This is just where the History of Timaeus left off; and it falls in the 129th Olympiad ... As to dates, then, I must fix on some era agreed upon and recognised by all: and as to events, one that admits of distinctly separate treatment; even though I may be obliged to go back some short way in point of time, and take a summary review of the intermediate transactions. For if the facts with which one starts are unknown, or even open to controversy, all that comes after will fail of approval and belief. But opinion being once formed on that point, and a general assent obtained, all the succeeding narrative becomes intelligible. It was in the nineteenth year after the sea-fight at Aegospotami, and the sixteenth before the battle at Leuctra; the year in which the Lacedaemonians made what is called the Peace of Antalcidas with the King of Persia; the year in which the elder Dionysius was besieging Rhegium after beating the Italian Greeks on the river Elleporus; and in which the Gauls took Rome itself by storm and were occupying the whole of it except the Capitol.

To get back to the question in a roundabout way, there's another reason I find it unlikely that people would have memorized the whole list of consuls. There are references to books or 'pocket calendars' or 'lists' of consuls and magistrates for easier reference. There is Livius, who refers to 'books of the magistrates' in IV,7,10:

During their consulship the treaty with Ardea was renewed. This is the sole proof that they were the consuls for that year, for they are not found in the ancient annals nor in the official list of magistrates (libris magistratuum).

Cicero makes reference to some a kind of private fasts of consuls in a letter to Atticus (IV,8a,2):

... that the future consuls take up as much pages in the list (fasti) in their letters (codicillorum) as the former...

So there were a lot of mnemonic aides available to turn some arbitrary reference like 'in the consulship of Albinus and Dexter' into a meaningful statement about a point in time.