How often should the tires need more air?
It depends on how many holes they have in them!
Seriously though, this air loss is normal. If you want optimal tire performance, even from a 40 psi tire, you have to fill up every day or ride which ever is longer. If you are using really high pressure tires, 100psi or more, you can expect some air to disappear everyday.
Rubber is actually porous and lets the air though. A great example you can see of this happening a lot faster is a balloon. I think for people with money to burn, in exotic cars, they fill the tires with nitrogen or C02. The molecules are larger and don't go through the rubber as fast allowing for less top offs, but you have to buy the stuff as opposed to pumping free air.