mAH is the capacity of the cell. A cell rated at (say) 75 mAH can supply 75mA for one hour.
Well, actually it's not that simple. the mAH rating is generally based on a 4 hour sidcharge (from memory) do this cell could give you 18.75mA for 4 hours. At 75mA it would actually give you slightly less than 1 hour service.
You'll also find rates specified as 1C 0.5C, 10C, etc. These relate to a current of that multiple of the capacity of the cell. So 1C would be 75mA, 0.5C is 37.5mA, and 10C is 750mA (for the example above). The C notation is very commonly used for describing charging rates, and for describing the characteristics of a family of cells.
AA cels were typically 400 to 450 mAH in the days that the HP41 was born. These days I can go out and get 1100mAH AA nicads.
The same is true (but to a lesser extent) with the sub C size. I can't remember the figures off hand, but 2300maH (2.3AH) seems to ring a bell. The newer, higher capacity cells will give you longer running time from a single charge, but a charge will take proportionally longer.
The best indication of a full charge is a rapid rise in temperature. I once posted the temperature of a full HP97 pack as I charged it. The rapid rise in temperature indicated to me that a 24 hour charge was WAY too long.
It's also important to note that higher capacity NiCads are more sensitive to overcharging.
If you look carefully into nucads, you'll find that they make nicads for rapid charge/discharge, trickle charge, etc. They vary in capacity since the use characteristics (partially) determine how they need to be constructed and where the tradeoffs in terms of capacity vs. ruggedness need to be made.