Historians and the general public choose it. The term for these names are epithets. Specifically, the ones you mentioned are cognomens, since they go behind (or before) the given name. In contrast, a sobriquet replaces the proper name altoghther.
Like us normal people, important figures do not generally get to choose their own nicknames. Instead, it is usually invented by someone else and then bestowed on them. Some of these caught on, so to speak, and continues to be known today; though many have since vanished from public consciousness.
One way this happens is that a chronicler or historian created a nickname in their writings. For example, Infante Henrique of Portugal was styled"the navigator" in the writings of 19th century German historians, Heinrich Schaefer and Gustav de Veer. This nickname was then popularised by the British writers Henry Major and Raymond Beazley, becoming standard outside of Portugal.
Sometimes the nickname was bestowed out of political motivations. For example, Julian the Apostate received his epithet from the early Christian Church for abandoning Christianity. William the Wicked, a relatively benevolent king, seemed to have been a victim of his biased chronicler's hatred.
Alexander the Great may have gotten his epithet from the Romans, who slowly came to appreciate his achievements.
It took a long time before Alexander's greatness really came home to the Romans, although they were the people who, as far as we can tell, gave him the epithet 'the Great', and it took even longer before he made an impact on individual Romans. The earliest record we have of Alexander is in Plautus' Mostellaria, 775-7, where the slave Tranio brackets him with Agathocles, tyrant of Syracuse: Alexandrum magnum atque Agathoclem aiunt maxumas
- Den Hengst, Danièel. Emperors and Historiography: Collected Essays on the Literature of the Roman Empire by Danièel Den Hengst. Vol. 319. Brill, 2010.
So in conclusion, the general public chooses these nicknames. But this does not have to be unanimous at all. In fact, some times people have multiple nicknames. For example, Louis XI of France has been called both "the Prudent" as well as "the Cunning", after his tight spending and intrigues, respectively.
