Great question!
There are a great number of species of bacteria that can serve our tanks as "Beneficial Bacteria" and a good number of them are commonly found all over in our natural environment.
The most common and ample location to find them is in moist soil. It is likely that your garden in the back yard has MUCH more "Beneficial Bacteria" than your fish tank does.
Many forms of bacteria can also go into an inert stage. In this stage they can exist 'encrusted' on the side of a rock used in a tank long ago, and then once introduced into an environment with the right conditions can "reawaken" and go back to work.
I can't answer exactly what the most common pathway for them to ender a brand new set up literally is... but the short answer is bacteria is everywhere... and doesn't take long to get into a newly set up aquarium...
Futher detail...
Bacteria doesn't "reproduce"... it grows, at it's maximum size, splits in half creating two identical yet completely individual organisms... then each of them grows, then splits, then grows then splits...
Therefore a single bacterium can be introduced to a fertile environment, double, and double, and double... and colonize the entire system.
In a fertile environment with "unlimited" resources (water, oxygen & food)... bacteria will never die. It is not like an animal that is born, grows uo, grows old and dies... it just grows and splits, grows and splits...
Yet in our aquariums, bacterium die off all of the time, due to limited resources... certain areas of the tank that have more resources allow bacteria in that area to thrive/increase, which reduces the available resources in that area, causing the colony in tha tarea to decrease in size, allowing that area to again become rich in resources, etc, etc, over and over...
It takes a single bacterium 4~6 hours to go from newly formed to splitting... Therefore it takes a mature colony 4~6 hours to completely double in size.
When we start as new aquarium, and get our first lonely bacterium to land in the tank... 5 hours later we have two, well two can't do much, 5 hours later 4, 5 hours later 8, then 16... due to this nature of "doubling" it takes a while to get the ball (the cycle) rolling, but once it's mature... and we, for instance, remove a sponge and rinse it under the tap killing a large quantity of bacteria... as long as we don't kill more than 50% of the bacteria from our overall system, it will replace whateever we removed in 5 hours...
I completely agree there are a lot of myths, misunderstandings and uneducated assumptions about the bacteria in our systems. I highly encourage everyone to go out and learn as much as they can and come back to share what they've learned...
...and I also encourage those who are not willing to educate themselves to ease back on the flow or suggestions and leave that to those of us who are trying to learn...
Great topic Swede... I hope some interesting links are to come...