Like many settings with a multitude of heroes, it's a grab bag of virtually every possible origin.
First, you mention a lot of S-class heroes in the post, but these are considered the exceptions; people at what is otherwise an unreachable level of power. The following image is from the webcomic, chapter 67, which is technically a spoiler for people only following the anime or manga, but does not cover any real plot lines; it's simply part of detailing the origins of the S-class. But I'll spoiler tag it anyway:
Known or implied power origins include:
- Tank Top Master and Puri Puri Prisoner: Strength training.
- Super Alloy Darkshine: Strength training, but claims his was "different" from the previous two.
- Bang/Silver Fang: Martial arts training
- Zombie Man: Genetic and medical experimentations by Dr. Genus. His only power is immortality/regeneration, however; physically and mentally he's an average person.
- Metal Knight, Drive Knight, Genos, Blue Flame, Gatling Gun, etc: technological enhancements.
- Fubuki, Tatsumaki, and other espers: power had since birth, presumably genetic or otherwise "naturally occurring". It is possible to achieve higher levels of skill and power over time, by training.
- Flashy Flash and Sonic: Ninja training and techniques.
- Boros: The individual pinnacle of a race made intrinsically super strong by evolving in a harsh environment.
Of course we see many of the above (most of who are S-class, as they're the ones we have the most exposure to over time) achieve feats far greater than we would expect possible from things like strength training and martial arts.
There are a few other origins from the webcomic and manga that might suggest additional mechanics within the setting.
Saitama's power seems to originate from ignoring his limits to the point that he ceased to have any. Garou seems to almost achieve the same thing by the end of his arc, falling a little short but otherwise ascending to a level of power and skill that seems to surpass everyone but Saitama. The idea of an intrinsic limiter on power is key to the series by this point. It is reasonable to believe this is a fundamental mechanic of the setting, as it has been stated by both in-world characters as well as the "narrator". It is indicated that the extremely powerful beings just have a higher limit and have worked to reach it, and/or used experiments and such to increase it. Or in some cases simply being born at a very high level, like with Tatsumaki. Saitama and almost-Garou break the mold by breaking this fundamental rule of existence, and that's how they surpassed the unsurpassable S-class.
Gyoro-Gyoro created Lord Orochi (a manga and anime only character) through various unspecified experiments, and is confident they can reproduce the results with a sufficiently durable specimen; Garou is considered a candidate for surviving the process and surpassing Orochi.
But most tellingly and perhaps relevant for future arcs, Homeless Emperor attributes his power as a gift from "God". When he's telling this to Zombie Man he then has a vision of this "God", who says he's taking back Homeless Emperor's life and power. Homeless Emperor then (literally) combusts and dies before Zombie Man's eyes. Zombie Man is willing to believe there is some entity that gave Homeless Emperor his power, and is concerned about what this entity is up to. We have neither seen nor heard of any such entity since then, but it may come up in future story arcs. As such there may be some god-like being who grants at least some people and/or monsters their power.
Several monsters also profess that they had an intense obsession with something, which then transformed them. Such as Crablante, the first monster Saitama is known to fight (before he begins his training). Perhaps some heroes, like Watchdog Man, have a similar origin. Possibly the previous spoiler is relevant to such transformations. Otherwise, the best we can say right now is that the setting permits fairly arbitrary origin stories, in part because out-of-universe it is constructed as a parody and at times deconstruction of the (super)hero genres.