Man is this ever a complicated question! The issue of legitimacy dominates scholarship of the Julio-Claudian dynasty, and the only real answer is that each emperor had his own way of making himself legitimate, because each came to power under different circumstances. There were a few strategies, and I'll start with the most successful.

1. Groom your successor

This is how Tiberius and the "five good emperors" did it. They had long public careers under their predecessors, serving an important role in their administration (usually in the military). Tiberius made a name for himself leading the German legions, for example. These men also served as traditional magistrates and might be proclaimed co-emperor before their predecessor died.

2. Military control

Augustus became emperor by being the only guy left with an army. To a large extent all that other stuff about the republic is just PR. Vespasian, Septimius Severus, and Constantine are further examples. They all came to rule after civil war.

2a. Military Success

Most emperors felt compelled to have military success. This was something that made the people appreciate them and showed divine favor. Hence Claudius bragged non-stop about conquering Britain. Triumphal arches were a permanent way of showing how successful the emperor was. Things like improving public infrastructure had a similar effect.

3. Displaying Personal Power.

The emperor was so powerful that he didn't have to play nice with the constitution. Caligula and Nero used their immense wealth to remind the aristocrats at Rome just how far beneath the emperor they were. This didn't so much legitimize them as it de-legitimize any potential rivals.

4. The Lex Imperio

Every emperor had to be publicly proclaimed emperor and had his powers enumerated in a lex, a law voted on by popular vote. The only solid evidence we have for this is an incomplete copy of the Lex de impero Vespasiani.

The bibliography for this question is huge, so I'll give you my favorite take: Winterling's Caligula: A Biography.

Okay, before this thread gets derailed completely, let's have a look at what was going on, starting off with what Augustus himself tells us:

In my sixth and seventh consulships [28 and 27 BCE], when I had extinguished the flames of civil war, after receiving by universal consent the absolute control of affairs, I transferred the republic from my own control to the will of the senate and the Roman people. For this service on my part I was given the title of Augustus by decree of the senate, and the doorposts of my house were covered with laurels by public act, and a civic crown was fixed above my door, and a golden shield was placed in the Curia Julia whose inscription testified that the senate and the Roman people gave me this in recognition of my valour, my clemency, my justice, and my piety. After that time I took precedence of all in rank, but of power I possessed no more than those who were my colleagues in any magistracy. (Res Gestae, 34)

You seem to have missed a particular step when looking at this event, which may be part of the reason for your confusion, namely that the senate created the position for him. It is true (well, in a sense at least) that Augustus didn't create the position for himself, but it was created for him, he was made emperor in all but name. What that means is that Octavian recieved the full legal rights for the position he was given. Legal rights that were improved during his reign, while the senate's powers gradually diminished.

Now, here's something very important for the whole Julio-Claudian dynasty:

[...] The triumph which had been voted to him he deferred, but granted to Octavia and Livia statues, the right of administering their own affairs without a guardian, and the same security and inviolability as the tribunes enjoyed. [---] (Dio Cassius, 49.38.1)

This is what essentially gives the Julio-Claudian dynasty its right to put forward heirs, although these powers aren't that important until about eight years later (27 BCE) when Octavian is given the title of Augustus. You may wonder what this means? Well, the Roman custom required each woman to have a guardian. Before she was married that was her father, if her father died, it was her brother, and so on. When she married the guardianship transferred from the former guardian to her new husband. In 35 BCE, when the above quote took place, Augustus and Livia had been married for three years, but Octavia had not yet been banished from Rome (an event you may have heard of).

Now, Augustus only had one child of his own, a daughter named Julia who later was married to Agrippa - Octavian's right hand. Since Julia was the daughter of Augustus, she would legally be the heir for the imperial throne, but as a woman she couldn't possibly have that position, meaning that the right would fall to the children of Julia and Agrippa. These were two boys - Gaius and Lucius (born in 20 BCE and 17 BCE respectively), and both them were adopted by Augustus at a rather early stage as heirs to the throne. However, Lucius died in 2 AD and Gaius in 4 AD (their father, Agrippa, died in 12 BCE), leaving Augustus without an heir once again.^1 When Agrippa died, Augustus forced Tiberius (who was the son of Livia from her first marriage) and Julia to marry. When Gaius and Lucius had died, Augustus adopted the last son of Agrippa and Julia - Agrippa Postumus - who had been born after Agrippa's death; he also made Tiberius adopt his brother Drusus' son Germanicus. Tiberius also gained (again) tribunician power.

In 13 AD, Tiberius was given equal powers to those of Augustus and when Augustus thence died in 14 AD, Tiberius legally became emperor as Agrippa Postumus had been murdered:

The first crime of the new reign was the murder of Postumus Agrippa. Though he was surprised and unarmed, a centurion of the firmest resolution despatched him with difficulty. Tiberius gave no explanation of the matter to the Senate; he pretended that there were directions from his father ordering the tribune in charge of the prisoner not to delay the slaughter of Agrippa, whenever he should himself have breathed his last. [---] (Tac. Ann. 1.6)^2

Tiberius was, as far as we're concerned, Augustus' last resort for an heir. Surely he could've adopted just about anyone else had it been needed, but as is, his final choice fell on Tiberius, who happened to have a very strong claim to the imperial seat. He was born a Claudian, which was one of the really old Roman families, because both Livia and his father - Tiberius Nero - were from separate lines of the Claudian family tree. He was thus also the son of the empress of Rome, and when Augustus adopted him as heir, he also became the adoptive son of the heir of Rome. So you can see that in the end, he was a person with a great claim to power.

Moving on, the following three Julio-Claudian emperors could in some way claim to be descended from Livia, which is were they got their claim to the throne. Thus a continuity of Roman emperors being rightful heirs was created and it actually followed in that way until the reign of Pertinax - who bought the throne from the praetorian guard, but that's as far forward as the late 2nd century AD, so let's leave that be. There are a few exceptions of course, like the year of the four emperors where military power played a rather prominent role, which ended with Vespasian taking power - seemingly by simply being a really great leader. Also the assassination of Domitian, after which the senate gave the title to the elderly Nerva.

That's the legal rights and family ties that made the imperial succession possible, but there was more. Because this is starting to take up a lot of space, I think I'll shamelessly add in a link here to a post I wrote a few months back, about Pax Romana. Propaganda was a great tool for justifying the imperial position and especially the Julio-Claudian reign is riddled with propaganda in different ways. Other periods had great propaganda as well of course, the Flavian amphitheatre (Colosseum) is a rather well known monument for instance. During the long reign of Augustus and Livia they both played their separate roles in being what we today might describe as "the perfect couple". By that I don't mean that they would have been the perfect couple in modern eyes, but that Augustus played the role of the ideal male citizen in the Roman world and Livia played the female counterpart. Bear in mind that the vast majority of Roman citizens would not see the emperor or the empress once during their lifetimes. Instead they would see monuments, altars and temples erected for them, statues and coins depicting them, decrees celebrating their deeds, etc. These depictions wouldn't have been completely truthful (think of a cover for a Vogue magazine where there is photoshopping, lightening and make-up making the person into an icon), instead these would be the kind of images they would have of their emperor and their empress. Livia's different hairstyles even became the ideal of other Roman women.

While you can't neglect the military power exerted by the emperor, I don't believe too much emphasis should be put on that aspect. Military power is great for controlling the great masses - as history shows us - but being popular with the people works better. The Roman empire also has a particular part in its history where it's ruled by "the Soldier emperors", which is essentially some 60 years of it being ruled by people with the highest command of the army. Hence why I don't put too much emphasis on it for the rather easy succession of the first ~200 years of imperial rule.

(cont.)

To piggyback on this somewhat, I asked a long time ago and never got a response on the question of whether or not there was a "sea change" following the last Civil War and the victory of Augustus when the average Gaius on the street realized the Republic wasn't coming back. Did people hold out hope that maybe once Augustus died, the "good old days" of the Republic could be restored by the Senate?

The position of emperor was more of a collection of powers and titles conferred upon the man by the Senate.

Among these are imperium, command of the armies; pontifex maximus, the head of the state religion; and censor, which gave him power over the membership of the Senate.

But, whatever the emperors may have claimed about legitimacy, the armies, and especially the Praetorian Guard, were integral in making and breaking emperors. It isn't for nothing that Septimius Severus' last words to his two sons were "Be harmonious, enrich the soldiers, and scorn all other men."