Besides the 512 bytes of EEPROM, you can also store things in program space, using some of the 8K flash that's normally used for programs.
If I want to know if bit 3 is on in an integer, I can do this:
long int i;i & 0x4
if (i & 0x4)
// code for "on" case goes here
is a logical and, the result of which will be 0x4 if bit 3 is on. Since 0x4 is nonzero, the logical expression for the if evaluates to true.
If you are using shift registers, though, you'll probably want to shift the values out of the long int in series, not pull out one bit at a time. I think you can use the SPI hardware to feed shift registers that way, but I haven't tried it myself.