When should I write to EEPROM?
The ATmega328 data sheet, in section "8.4 EEPROM Data Memory" says
The EEPROM has an endurance of at least 100,000 write/erase cycles

So a reasonable strategy should be okay.


Wait at least 30+ seconds after the last change, before considering a write. When I futz with the volume, it is to mute advertising. Also I often increase volume to hear something specific, maybe a favourite track, then re-set volume quite close to where I started. If you haven't implemented a mute, it might be worth doing so. That is a common case for me, and might be a common case for you. You might significantly reduce the number of volume updates by ignoring mute, and leaving the saved volume unchanged.
Don't write if the value is only a couple of % different. It is unlikely that your ears will tell the difference.


If the number of writes/day is still an issue, detect 'power down', and change the strategy to only saving when power is being removed. 

The chip will need several milliseconds to ensure it can do the EEPROM write. 
The best data I've found about EEPROM write time is "Table 28-18, Typical Wait Delay Before Writing the Next Flash or EEPROM Location" says the delay is "3.6ms". 

So the local power supply to the ATmega will need a maintain an operating voltage for longer than that to ensure EEPROM is correctly written. That might be a bit awkward to do on an Arduino. IIRC the power supply capacitance within the power supply is about 100uF, which is marginal, and probably too little to be sure of doing the write, especially if any significant loads were being driven at the same time.