Other than SD (see @lesto's answer), you can also store the data locally on your Arduino's EEPROM. You can store a byte at a time. The amount of storage varies from chip to chip, the AtMega328p that powers Arduino UNOs has 1kb. The eeprom is persistent over resets, I suspect not if you're reprogramming it, so think how you're going to get the data off before you start storing valuable info.
At 1kb, size is at a premium, so you probably don't want to use text strings, just the raw data. Remember that, if your chip resets, you will lose any memory variables with info about e.g. where you're up to. I would probably include some sort of checksum of each record, to test if the data is yours or not. I would include a counter or timestamp, so when you are starting up, you can read all memory to find the newest (valid) record; the next record is one greater, and at the next memory address. When you get to the end of the memory, restart at 0. If you store a one-byte counter, a one byte checksum, and 2 bytes of data, you can store 256 records. You could mark records off as you send them, or keep a counter in memory of which ones you have already sent - if your chip is reset, it may resend old records (very rarely), which your server would need then need to handle.
If using eeprom, try to spread your writes - you get a certain number of writes PER MEMORY LOCATION, so if you always write to address 15, then 15 will wear out before the others. I think I saw a reference to "100,000 writes", but am unable to find that now to confirm. 100,000 writes at 1 write per second to the same address will have your eeprom fail after about 27 hours; 4 writes per second spread over 1K will cause a fail after about 10 months.
Test what happens when you write past the end of memory - some possible scenarios include failed write, write to a different location (e.g. trying to write to address 1024+1 will write to address 1024), not writing at all and reading it back will return 0, 255, or another number (consistent or otherwise)
See http://arduino.cc/en/Reference/EEPROM on how to write to eeprom.
To find out how many bytes of memory your EEPROM has, use E2END. Addresses run from 0 to E2END, so E2END might be 1023 (0 to 1023=1024 bytes).