mrShrimp:
Ok, it seems like I will have to use an SD card. I definitely do not trust myself to make this from scratch, so would I be able to start with something like this: MicroSD card breakout board+ : ID 254 : Adafruit Industries, Unique & fun DIY electronics and kits, and interface it to a standalone ATmega328?
Yep, I have one of those and it is easy to interface. You just need 6 wires: +5V/Gnd and the other four go to D10 to D13 on the Uno (which is pins 16 to 19 on the Atmega328 chip itself).