The datasheet for the ATTiny13A, for instance, lists Min frequency of 0 MHz.  Does this mean the clock can be run at any arbitrarily low frequency with no ill effects?  I'm assuming it draws lower current at lower clock speeds?  Does 0 MHz mean you can stop the clock completely, and as long as power is still applied, it will remember its state indefinitely?
Yes. If the datasheet says "fully static operation", then you can clock it at any speed, even 0 Hz.  A "dynamic" chip needs to have a clock at a specific rate or it loses its state.