Why do people with type O blood have anti-A and anti-B antibodies?

To understand what's happening here, let's have a look at the actual ABH (or ABO) antigens:

As you can see, they are not very big molecules: quite the opposite, they are relatively small globosides.

That being said, how it's possible a type O individual producing anti-A and anti-B antibodies without having any contact with the antigens? And that is the same as asking "how it's possible a type A individual producing anti-B antibodies without having any contact with the antigen?"

The answer is: there was contact with the antigens, even without a blood transfusion.

According to Laura Dean (Blood Groups and Red Cell Antigens, chapter 5):

ABO antibodies in the serum are formed naturally. Their production is stimulated when the immune system encounters the "missing" ABO blood group antigens in foods or in micro-organisms. This happens at an early age because sugars that are identical to, or very similar to, the ABO blood group antigens are found throughout nature.

Thus, from an early age, we have contact with the antigens, coming from food or bacteria in our digestive system. As we get in contacts with antigens A and B, this is what happens:

• People with type A blood: they will produce anti-B antibodies.
• People with type B blood: they will produce anti-A antibodies.
• People with type O blood: they will produce anti-B and anti-B antibodies.
• People with type AB blood: they won't produce antibodies (regarding A and B antigens).

Source: Dean, L. (2005). Blood groups and red cell antigens. 1st ed. Bethesda, Md.: NCBI.

Antibody-producing cells (B lymphocytes) generate antibodies through a gene recombination process, that allows a virtually infinite number of antibodies to different antigens to be created, including against self-antigens (https://en.wikipedia.org/wiki/V(D)J_recombination).

A process of maturation, if working correctly, allows for those cells producing antibodies that strongly bind to self-antigens to be suppressed or eliminated, preventing autoimmune attacks (https://en.wikipedia.org/wiki/Immune_tolerance). In this process, specialized cells present a myriad of self-antigens to the maturing lymphocytes, signalizing them to undergo apoptosis or become regulatory cells if they bind to them. Organisms with the A antigen will present it to maturing lymphocytes and thus create tolerance to it, not having cells producing A-antigen binding antibodies; but they don't have the B antigen, so their lymphocytes won't be selected over it, and they will have cells producing B-antigen binding antibodies, which, if such antigen is introduced into the body, will mount an immune response against it.

Likewise, someone with an O type blood won't have both the A and B antigens, and so cells producing antibodies that bind to them will be allowed to mature, and they will have anti-A and anti-B antibodies circulating in the blood.

In conclusion, we can and do have antibodies for more antigens than we will ever encounter, and we have then before ever encountering them. If we do encounter them, then the cells that produce those antibodies will multiply and the number of those antibodies will greatly grow. Typically, we only don't have antibodies for self-antigens.