It was an age before photos, but they did have statues, coins, and frescoes. Were these enough to tell people who'd never seen the Emperor et all how to recognize them?
Probably not. I'm afraid there's not a huge number of stories to make a decent sample; rather a few anecdotes.
In the first place, during the Republican period most coinage had civic imagery, like the portrait of Roma or the Dioscuri, like this. Another popular deity was [Janus]http://numismatics.org/collection/1944.100.255?lang=en). The obverse is the prow of a ship. Ships captured in Punic 2 were used to decorate the rostra.
Moving into the middle and late Republic, using images illustrating family history became increasing popular. This one (I own an example of this myself - it's my favorite coin) depicts a heroic act the minter's grandfather accomplished during Punic 2 on the obverse. This one does carry the minter's name - M Sergius Silus - but that's also the name of the grandfather. This is also a special case, because usually a quaestor wouldn't strike coins; the aediles oversaw that for usual coinage; this one was a special run ordered by the senate, probably in response to a cash shortage. Anyway, you could advertise your family, but you wouldn't have your own portraiture on the coin - that's too close to Hellenistic kingship, where the kings claimed to be divine. In fact, the first living Roman to appear on a Roman coin was Julius Caesar. After Caesar did it, basically everyone started doing it, but I know less about imperial coins than republican ones.
As for statues, Plutarch gives us this interesting comment about Pompey:
His hair was inclined to lift itself slightly from his forehead, and this, with a graceful contour of face about the eyes, produced a resemblance, more talked about than actually apparent, to the portrait statues of King Alexander.
The implication is that people say Pompey looked like Alexander, even though he didn't.
There was an incident in the riots after Caesar's assassination:
They were so mad with rage and grief that meeting the tribune Cinna, on account of his similarity of name to the praetor Cinna who had made a speech against Caesar, not waiting to hear any explanation about the similarity of name, they tore him to pieces like wild beasts so that no part of him was ever found for burial.
I'm not entirely sure what happened here. Our source, Appian, makes clear this is mistaken identity based on someone having the same name as the target. I'm not sure how they got poor Cinna's name, but in any case it's clear the mob couldn't distinguish between the tribune Cinna and the praetor Cinna.
During the second round of proscriptions, we get this story:
Salassus escaped, and, not knowing what to do with himself, came back to the city by night, thinking that the danger had mostly passed away. His house had been sold. The janitor, who had been sold with the house, was the only one who recognized him, and he received him in his room, promising to conceal him and feed him as well as he could.
Now, in other cases statues and busts and stuff were used; Plutarch describes Sulla's features based on a statue, but Plutarch was elite, and he doesn't say what kind of statue he was looking at, public or private?
Back in the proscriptions, there's an interesting case of both recognition and lack thereof.
Aemilius, not knowing that he was proscribed and seeing another man pursued, asked the pursuing centurion who the proscribed man was. The centurion, recognizing Aemilius, replied, "You and he," and killed them both.
Aemilius is a very aristocratic name, and the guy was important enough to make the proscription list, but he doesn't recognize the other guy, yet the centurion recognizes them both.
Here's one about a former consul:
The inhabitants of Minturnae were scouring this marsh in search of robbers, and the agitation of the reeds revealed the hiding-place of Varus. He was captured and p189 said that he was a robber. He was condemned to death on this ground and resigned himself, but as they were preparing to subject him to torture to compel him to reveal his accomplices, he could not bear such an indignity. "I forbid you, citizens of Minturnae," he said, "either to torture or to kill one who has been a consul and — what is more important in the eyes of our present rulers — also proscribed! If it is not permitted me to escape, I prefer to suffer at the hands of my equals." The Minturnians did not believe him.
Recognizing someone by sight was very hit-and-miss. If you're elite enough (centurions apparently), you hobnob with enough wealth that you might be able to recognize someone by sight, but other people might not. I've noticed, reviewing these accounts of proscriptions, it's often someone who knows the victim personally that tips off the soldiers.