Since there had been other answer tell you about how all this legitimacy business works, I will provide some information on why did this situation happened. Because under normal circumstances, none of that is going to fly with the imperial court. Three kingdoms era isn't a normal circumstances.
There was certainly a institution in place with government, rank and whatnot, even the Han Emperor was still around until 220 CE. But it were a mere empty shell, the authority to enforce that system has long collapsed; the empire's officers obeyed it in name only and straight up ignored it whenever opportunities arise.
Before the fall: Institution of the Han
Firstly, let turn back in time a few centuries. The first centralized states in China, established by Qin Shihuang, did not outlive its creator for long. It had fallen to a massive rebellion merely 3 year after his death, followed by a bloody civil war between the rebels. Few would expect Liu Bang, a man of peasant origin, would be the one to came out on top. And where Qin Shihuang failed, Liu Bang succeeded; his new dynasty managed to endure 4 centuries and its legacy remain in Chinese identity even today. As a political institution, the Han dynasty is a centralized state in every ways. It is ruled by the Emperor, with the imperial court to advise him and handle the bureaucratic works at all levels from center to local. If you are peasant living in a Han empire's province, the one in charge is likely to be civil servant that were hired by the imperial court, paid a salary, and would hand back his position upon retirement (or being sacked). Landed, hereditary nobles still existed as "Marquis" and "King", their titles only contained the right to a stipend of their fiefdom and not the right to rule it (Liu Chong, king of Chen was one exception as he is actually allowed to rule his fief and defend it with his personal army). The imperial court's bureaucratic system would handle it for them. "King" in particular are only granted to member of royal families, after many many crisis, the Han had made their point not awarding this title for outsiders.
Before the Three kingdoms era kicked in, we were looking at around 150,000 civil & military officers, filling different positions with according duty and salary rank. At local level, there were 13 provinces, each consisted of a number of commanderies. Each commanderies is led by an Administrator (太守) who will well ...administrate the land at a 2000 shih (bushel of grain) salary. If that commanderies also had issues with rebellion or invader's raid, there would also be a Commandant in charge of the local stationary troops, and report to the Administrator; otherwise, Administrator was a purely civil job and has no say whatsoever in military matter. At province level, there was an Inspector (刺史) who supervised the Administrators in that province. Inspector received a salary rank of 600 shih, actually a much lower rank than Administrator, and didn't really have any legal power in the province other than reporting their action to the imperial court.
Sometime there would be another position called Shepherd or Governor (州牧) replacing Inspector. Governor also received 2000 shih and has legal power in his province, all constituent Administrators will report to this man. And the Han statecraft would dangling between these two models for the length of its existence. Inspector would to restrict the local authority, ensure none of them have too much power while Governor strengthen it, allow better flexibility in time of need but also increase the risk of decentralizing the power structure.
But when threat escalate outside of the local's capacity, the imperial court's would certainly response with force. According to its conscript policy, all able bodies had to spend 2 year in the military. They could be excused from this service by paying military tax or contributing food, horse... to the government; otherwise, they had to train for 1 year in their home commaderies, then served for another year as actual soldier at wherever they are assigned to. After which they will be released from service or keep working as a professional soldier. The most prominent fighting force are the Northern army, consisted of 3500 professional soldiers commanded by 5 colonels under direct paycheck from the goverment treasury; charged with guarding the capital and works as a quick response forces against rebel. Other than that there were encampments at strategic locations, the size of which could reach 1000 men each, the capital city also often form and train various reserve forces like the palace guard, the Cavalry of Feathered Forest, the West Garden army... In any case, the Han didn't actually keep a very large standing army and they are quite spread out to guard the empire. It is both for economic purpose and to reduce the risk of a general who command too many troops may start a coup. When specific need arise, the imperial court could ordered the mobilization of an temporary campaign army, enlisting soldiers from its 50 million population, many men of which had been through military service. The empire may be slow, but it is an intentional design and when it moves, you better get out of the way.
To add to what u/handsomeboh said
There was the Han still under the (bar a very brief spell where he escaped Li Jue) controller Emperor Xian till his abdication in 220 and till that point, most warlords, paid a degree of lipservice to it. They took what ranks they had when the civil war start, took any given by the Han controller if it suited then started then anything else, they memorialized the throne on taking greater rank and justifying their control of regions.
If it suited, the controller of the Han might later grant such ranks (or lesser ranks then they hoped to seek to reign them in) and thus making it offical, if not well it was the wicked controller of the Han getting in the way of the true Sovereign and it would be recognized some day.
To add legitimacy where possible, another warlord might agree to nominate his ally for the role or gie backing to it. Liu Bei sent to Yuan Shao seeking his backing in taking over from the dead Tao Qian in Xu and was backed by Kong Rong of Beihai, Yuan Shu and Liu Biao supported each others ranks (administrator of Nanyang and Governor of Jing) at the start of the civil war, Liu Bei (also Liu Qi) and Sun Quan supported and memorialized to the throne each other ranks following victory at Chibi as they sought to take Jing from Cao Cao.
Only two times did major powers broke away from "Emperor Xian is the Son of Heaven" before the Han fell.
Sometimes the Han controller would attempt to replace a warlord, nominating someone to take over as Governor/Inspector of their home base. This didn't usually work though the person sent in could cause trouble by allying with discontented local powers. Liu Yao was the most successful, he couldn't take over Yang from Yuan Shu but he went across the Yangzi, gathered support from refugees from the north and local families then seized control of the south from Yuan Shu's officers Sun Ben and Wu Jing for a time till Sun Ce eventually breached the River.
In terms of becoming Emperor's, all three sought to justify via ritual, prophecy and arguments their foundations as legitimate. Wei carefully orchestrated the abdication of Emperor Xian to Cao Pi, handing over the Mandate to a new dynasty. Liu Bei argued his was the continuation of the Han who had ruled for so long and were still the legitimate dynasty. Sun Quan had earlier broke with the calendar system, a prerogative of an Emperor, the Han was dead but there was nobody who taken up the throne legitimately, Heaven and his own virtue justified his being the one to step up.
In terms of ruler hierarchies, some junior allies did pay tribute like Shi Xie to Sun Quan and Gongsun Gong (and his nephew Yuan when convenient) to Wei but this wasn't usual. Allies as I said might join in and memorialize their ally should totally be governor of the place he currently holds and is a true loyalist.
Controlling the Han Emperor could elevate status as a warlord could seek to shore up legitimacy by tribute, hoping for ranks and enfeeblement to really legitimize their positions. When Cao Cao took control of Emperor Xian in 196, the only warlord to answer the Emperor's call for help, he did use it to boost his status. As controller of the Han, he could confirm your lands were 100% legitimate and Han approved and you were fighting for the Han against the rebels (who just happened to be mutual enemies). He could also give your relatives and your officers official rank though this was not always entirely welcomed by the warlords. However Cao Cao's initial attempt to overawe his patron Yuan Shao and ending up having to give Yuan Shao the rank Cao Cao initially claimed as Han protector showed there were limits to the power being controller granted him.
Yuan Shao in the early years of the civil war had a certain status due to his family being the leading family of the Han and having been leader of the coalition against Dong Zhuo. He appointed Zhang family officer Zang Hong to Inspector of Qing when Jiao He died and it was accepted by the other warlords, he was used to legitimize Liu Bei's claim in Xu and he may have helped Cao Cao become Governor of Yan. I struggle to think of anyone else with that kind of status or hierarchical position among the warlords.
Legal legitimacy was incredibly important to the various states of the Three Kingdoms period, and each hesitated to declare imperial ambitions for fear of being seen as an immoral usurper. There were several different ranks, initially officially coming from the Han court, and only much later did individual states claim legitimacy by themselves. This is best illustrated through several case studies:
Of the states which derived legitimacy directly from the Han Empire, none is more obvious than the Kingdom of Chen, which was ruled by Prince Liu Yong, the uncle of the Emperor, and one of the most powerful states before Liu Yong was assassinated by Yuan Shu. Even states like Shu Han, derived their legitimacy through Liu Bei's claim to descent from the imperial bloodline (漢室後裔), and this descent was pivotal to the strong alliance between Liu Bei and Liu Biao.
States which had nothing to do with the Han Empire still had to put up the pretence of virtue by linking themselves, forcefully if necessary, to the Han Empire. None show this more obviously than Cao Cao, who kept the Emperor hostage so as to legitimise his actions (挾天子以令諸侯) like being made King (against the law which prevented non-Liu family members from being made kings), and refused to declare himself Emperor even after the other two states already did. Tellingly, until the late Three Kingdoms period, no ruler even dared to declare themselves kings, let alone Emperor. Yuan Shao was clearly the strongest warlord at the beginning, but he retained his Marquis rank (侯) until his death.
Perhaps the best case study is what would happen if one became perceived as a genuine usurper with no legitimacy, exemplified by Yuan Shu. By proclaiming himself the Emperor with minimal strength and support, Yuan Shu pissed off everyone all at once. His best generals like Sun Ce defected immediately, and within months Cao Cao could seize half his country without fear of reprisal.