Gaius Marius was famously short-changed in the name department compared to other Roman Republican generals - he had just a praenomen and nomen. No congnomen, nothing grand-sounding to commemorate his many victories.
His first mentor, Publius Cornelius Scipio Aemilianus Africanus, was perhaps slightly over-named, since his name included Aemilianus from his birth father (Lucius Aemilius Paulus Macedonicus), as well as the names of the uncle that adopted him (Publius Cornelius Scipio Africanus). Lucius was merely an Aemilius Paulus until he conquered Macedonia (Battle of Pydna, 168 BC) - as well as loot, in those days generals got to add their conquests to their names. Likewise, his adopted grand-father Scipio got Africanus after defeating Hannibal (Battle of Zarma, 202 BC). The Scipiones were of course a branch of the gens Cornelia - the vast patrician family that also produced Sulla, Cinna and Caesar's first wife. The congnomen Scipio, first recorded when the Gauls invaded Italy in 395 BC, showed which branch they were from.
These extra little eulogising nicknames are known as agnomina (singular: agnomen) and tended to be victory titles. A country would do (Macedonicus, Britannicus, Germanicus), but a continent was better - Scipio got Africanus, his brother became Lucius Cornelius Scipio Asiaticus after the Battle of Magnesia (190 BC). America had not yet been discovered, so there was no Americanus.
Because sons were named after fathers, and there was a shortage of good patrician names, a different type of agnomen came into use to differentiate branches within a family. Often a 'trait' was used - such as hair color or personality. Pius for a 'pious' branch of the Caecilii Metellii. Caesar for an obscure cadet branch of the Julii. Africanus was known for his love of women - and had he not defeated Hannibal, the good general could have been given an epithet reflecting this.*
'Pius' is Quintus Caecilius Metellus Pius, son of Quintus Caecilius Metellus Numidicus. The latter's agnomen or victory title - Numidicus - is highly dubious, since Marius was the victor of the Numidian War, and the great general who defeated Jugurtha. Unfortunately Rome was then still an old patricians' network, and the Senate had arranged for the 'people' to acclaim Quintus Numidicus. Later Sulla would try to claim the credit for the defeat of Jugurtha - although not until he had long fallen out with his mentor, and become a rival of Marius'.
Quintus Lutatius Catulus - despite having had to retreat in a panic, and losing, gosh, a good chunk of his army - would try to claim the credit for Vercellae (101 BC), and the defeat of the Germans. So we have Marius, the Saviour of Rome, the New Founder of Rome, the First Man in Rome, the man who reformed the army, defeated the Germans, and the Republic's great general .... not having won a single victory, according to his rivals.
Marius made his lack of grand names into a virtue - he was a simple Roman, just like the men he led, and he made a point of this in his speeches.
After Marius most generals developed more and more grandiose names. Pompey awarded himself the epithet of Magnus - but fortunately lived up to it. The trend continued into the early modern period, but has since died out, which is a pity.
Yesterday I was having the same conversation everybody else is probably having - who do we think that Senators Obama and McCain will pick as their VP candidates. My friend mentioned 'Clark' for Obama. Clark? I couldn't at first think who she meant, then I realised that she meant General Wesley Clark. The problem with Clark, is that it's a popular name, and not distinctive enough. We should bring back agnomina for generals - Clark Kosovicus? Clark of Kosovo?
* Caesar also loved women. So did Sulla. Perhaps this is another Republican trait that we should also encourage in our generals? The US is after all meant to be new new Rome, and the Founding Fathers deliberately modelled our institutions and the Constitution on Republican Rome rather than Athens.