Most male Roman elites had three names: Praenomen, Nomen, and Cognomen. The Praenomen (Gaius) was a personal first name. The Nomen (Julius) is the name of an extended family or clan (gens). The Cognomen (Caesar) indicated a smaller group belonging to the gens. Not all Romans had a cognomen - Gaius Marius doesn't seem to have had one for instance.

In addition there are agnomen - additional names that make a person further notable. So Publius Cornelius Scipio, when he conquered Carthage, became Publius Cornelius Scipio Africanus in recognition of his military feats.

You might also get an agnomen to mark an adoption. The second son of L. Aemilius Paullus was adopted by Africanus' son (also P. Cornelius Scipio Africanus - agnomen can be inherited) and by adoption became P. Cornelius Scipio Aemilianus - the agnomen Aemilianus indicating the family he was adopted out of. He also inherited the agnomen Africanus, and eventually earned his own, Numantinus. The entry the Oxford Classical Dictionary lists him under is Publius Cornelius Scipio Aemilianus Africanus Numantinus.

So for Augustus, he was Gaius Octavius, but when Caesar adopted him in his will, he became Gaius Julius Caesar Octavianus. Augustus the OCD says was a title more than a name.

Girls just had the name of their gens (Julia, Cornelia) and their praenomen were often numbers (Secunda, Tertia).

It's really not that hard once you learn the system. The confusion comes for me when people switch between which name they use. I'm reading Cicero's De Re Publica, a dialog between Scipio Aemilianus and some of his friends. The text alternately refers to Aemilianus as Scipio or Africanus, and I keep having to remind myself this isn't the Africanus that beat Hannibal.

Here's a quick guide that I use.