do Higgs Bosons happen in nature all the time? Rarely? Or do they only happen when the Higgs field is excited in a particle accelerator?

The Higgs field is a scalar field and it happens that the vacuum expectation value of that field is non-zero in our universe. It is this non-zero Higgs vacuum expectation value that gives the elementary fermions of the standard model of particle physics their rest mass. Now this Higgs field is a scalar so it is as if there is a single numerical value that specifies this field strength everywhere in space.

If you think of this scalar value as being like a the depth of the water in a swimming pool, then the Higgs Boson is like waves on that water. So a Higgs Boson causes small up and down variations in the Higgs value as it travels through space. And as a particle, it takes 125 GeV of energy to create the Higgs Boson. So the Higgs Boson can only be created where that much energy is available. Cosmic rays hitting the earth have energies that high and much higher so it is certainly possible for cosmic rays to be creating Higgs Boson particles independently of the LHC or any other human particle accelerator. However, these Higgs Bosons are certainly not bombarding every particle all the time.

However, I think what Dr Cox is talking about is the Higgs scalar vacuum expectation value that fills all of space. That is what is giving elementary fermions their rest mass, but this is not at all the same as the Higgs Bosons that were created and detected at the LHC. So I think Dr. Cox was taking some liberties to try to explain this complicated physics to non-physicist audiences.

You need to distinguish between real and virtual particles. The photons resposible for the em force are virtual. Similarly for the higgs. It needs a lot of energy to create a non-virtual higgs, about 125 GeV.