Thats very helpful, thanks!
So from looking around, it seems that an SD card speaks SPI natively and all we need to do to talk to an Arduino is voltage level conversion, either with a level converter chip or some resistors. I found this part on SparkFun:http://www.sparkfun.com/products/136
I also found this board:http://www.sparkfun.com/products/9802
This one just has a level converter chip to change the 5.0V signals to 3.3V. Ther is also a lot of info here that implies this is the case.
I am also looking to see if I can use a CF card. I'm actually trying to figure out all the differences between SD, MMC, microSD, CF and so on.