Storing data (strings) if ethernet fails to send it Flow goes something like:

Read sensors
Send data
If send fails store the data in eeprom/flash/sd
If sent check if any previous ones have failed and send those

So my question is what's the best storage option to save the data? Is there an easy way to save strings or am I going to have to write it byte by byte?
In my opinion SD would be the best way because it is cheap, small, relatively fast and easily portable on a PC, using FAT (but it uses a lot of resources) or even raw; but then you have to use some more trick to get to the raw data from a OS, its not just "plug n read".

The SD library uses FAT under the hood, and it gives you a nice and easy interface. Just remember that SD works at 3.3V, and connecting them directly to arduino will break them fast, even if often not immediately.