Based on the ages of the actors, and the fact that Max was old enough to be a cop in the "old world", I'm under the impression that less than 20 years has passed since the the apocalypse happened and/or began.
Within Immorten Joe's citadel there is a relatively sophisticated, complex society. The war boys are completely indoctrinated in Joe's faux-Norse religion and are willing to sacrifice in their lives in trivial ways to make it to Valhalla. They have a complex style of fighting that would clearly require a lot of training to be effective at. I mean, I doubt even the highest level special ops Navy Seals have to deal with such (visually stunning to be sure) absurd styles of warfare. That's not to mention the freakin pole cats from the bullet farm that are just bungeeing left and right with chainsaws. Even if the soldiers are all 14-18 and were raised in these societies from birth, I feel these societies would have to already have been going strong for many years previous to the birth of the current warrior generation for the boys' education/training/indoctrination to have a chance at being effective.
This is the only Mad Max movie I have seen, so perhaps some of these answers are provided in the Mel Gibson films. Though, I know it is not intended to be a bona fide direct sequel - one article described it has having the kind of continuity that happens when Bond actors are switched out. So from that I gather everything from the established cannon is assumed to be cannon with a big grain of salt that it could be completely changed or things could be retconned at the whim of the director (at which point it becomes cannon for that actor's series of films).
My speculative explanations:
The apocalypse is not a singular event, but an era happening over the course of maybe a century. (Un)Mad Max is born during the thick of that era. There are still normalish societies, but everything is deteriorating and you can't rely on the rule of law even in "advanced" countries. Mad Max is a cop in this deteriorating society and after his family is murdered he just doesn't see any point in staying around. So Immorten Joe's society could have been developing for a hundred years, which explains its bizarre, yet strongly reinforced culture, as well as the complex training the soldiers must get, and the intricate symbiosis it has with the bullet farm and the gas place (forget what they call it).
Max is an Aragorn-style superhuman that is a bit faster and stronger than the usual human, and lives for hundreds of years but otherwise appears like a normal man. He was a cop before the apocalypse, AND Immortent Joe's society has developed for a plausible amount of time.
In some ways the film is framed as a legend being told once society has been rebuilt. Maybe, like some suspect with Bond*, Mel Gibson and Tom Hardy are separate Mad Maxes, but because they are old legends many of their details get conflated. So maybe Tom Hardy wasn't ever a cop, but the fact that he was distinct from the Max that was a cop has been lost to history. Sort of like how Achilles has a different origin story depending on which Greek myth you consider the most convincing*.
Answers that use examples from real life would be awesome. I know cults can develop in very short periods of time and involve large numbers of people a la Jonestown. Perhaps, besides the fighting, something like Fury Road isn't all that implausible
* I am not well versed in James Bond or Greek mythology so these assertions may be completely wrong.