How can software give an accurate estimation of remaining usage time for a worn battery?
The way that the estimations for remaining time work using either historical data and / or current being drawn from the battery of a known capacity, or most usually a combination of the two. 

Most laptops and systems will be able to ascertain charge current and discharge currents at a given moment, these values may come from a current sensor OR often by reading the % charge status over time, and a known 'full' capacity, and estimating the current draw (or charge current, etc). These readings are usually time-moving-averaged over several points to provide the estimate of remaining time based upon the usage conditions at that point in time.

With respect to the precision, they are rarely THAT precise TBH, though with the accumulation of past data they can become usable in the way you describe.

If they have battery voltage and an estimate of current, then power usage of the entire system become trivial to calculate. (Again this is just an estimate)

With respect to battery 'wear', this is generally more calculated by the amount of charge that has been successfully put back into the battery in, versus a known 'full' capacity. A lithium battery will be charged initially at constant current, and then switch to constant voltage later on. I am not sure where on the the charge 'curve' they would usually take the reading for wear, but my suggestion would be that the simplest approach would be to record the point at which CC switches to CV, however systems that can record the current and voltage, would be able to integrate the charge curve to provide the actual charge inserted into the battery, and this would be far more accurate.