Is EEPROM persisted across program flashes? If I use EEPROM.write(someAddr, someValue) to write a value to an address, how long will that value "stick" to that address before being lost?

If I were to power down the Arduino, flash a whole new program to it, and power it on, could I still retrieve that old/cached value written from the previous program?
Only if the EESAVE fuse is programmed (it is unprogrammed by default). If not then the EEPROM will be erased when a chip erase command is performed.