There's no easy answer. It depends on a few variables:
- The stress you've exposed your muscles to.
- How close you are to your genetic potential.
- How good your recovery is.
You (probably, based on your fitness as explained) could do 20 pushups a day, every day, and have no problems. However if you tried to push your 1RM (single maximum effort) bench press, you would not be able to do it again tomorrow. If you can, after you lift enough and get strong enough, you won't be able to. Eventually if you continue to get your strength high enough, you won't be able to repeat your maximum lift twice in a single week.
Basically the stronger you get, the more damage you can inflict on your body. Granted you get better at adapting, but not at the same rate. This diagram below shows it a bit:

The stronger you get, the harder you are training overall, and the heavier you work, the longer it will take to recover and achieve overcompensation.
Probably the biggest reason folks use real training programs (Starting Strength, Madcow, Texas, 5/3/1, etc) are because they attempt to thread the needle on lifting as much as possible while never exceeding your recovery (basically).
If you're on a structured program you'll know if you haven't recovered: you simply won't be able to lift the weights as prescribed. If you can, congratulations, you're stronger.
Also, soreness is a terribly inaccurate measure of workout effectiveness.