Project for small underwater pressure and temperature sensing feasible?

I've never tried to connect an Arduino to a phone, however I've used SD cards on several projects and the program is very easy. Arduino has a built in (or add in) library for SD cards. All you have to do is purchase a SD board. like one of these (also look on eBay)

Here is the code I used to verify the SD function on my M0 board:

/*
  SD card read/write
  Mod 01 make file name a string and iterate until we find a unused file name.
  Mod 02 add capability to increment filename.
  Rev 03 tested successfully on Arduino M0

  SD card attached to SPI bus on ICSP Header.
  SD Board power = 5V (for large board with EEPROM)

  based on code created: Nov 2010 by David A. Mellis, 9 Apr 2012 by Tom Igoe
  This code is in the public domain.

driver has a 512 byte buffer then write to SD

Closing the file forces any buffered data to be written to the SD and also updates
the file's directory entry.

If you don't close the file, you will lose all data written the file since it was opened,
not just the last buffer, since the directory entry will not be updated.
*/

#include <SPI.h>
#include <SD.h>

// *** SD Card declarations **************************************************
// ***************************************************************************

#define SDCARD_CS_PIN 4

uint8_t fileNumb = 100;
char dataFile[8];
bool SD_Error = false;

File myFile;			// create instance of a "File" class

void setup() {
  SerialUSB.begin(115200);
  delay (2000);
// Initializing SD card....
  if (!SD.begin(SDCARD_CS_PIN))
    {SerialUSB.print("initialization failed");
     SD_Error = true;
    }

// loop until we find a file that doesn't already exist.......
  do
    {
     itoa(fileNumb, dataFile, 10);  // (value, Array, base)
     const char *extension = ".csv";
     strcat(dataFile, extension);  // syntax  strcat(dest, source)
     ++fileNumb;
    } while (SD.exists(dataFile));


SerialUSB.print("READY TO OPEN FILE FOR WRITING   = ");
SerialUSB.println(dataFile);
  myFile = SD.open(dataFile, FILE_WRITE);   // <<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<
SerialUSB.println(myFile);
  // if the file opened okay, write to it:
  if (myFile) {
    myFile.println("data from boiler");     // <<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<
    SerialUSB.println("data from boiler");
    //SerialUSB.print(" data written to file:   ");
    myFile.close();                         // <<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<
 SerialUSB.println(dataFile);
    }
  else {
    // if the file didn't open, print an error:
    SD_Error = true;
    }
  SerialUSB.print("SD_Error = ");
  SerialUSB.print(SD_Error);
}
void loop() {
  // nothing happens after setup
}

You should also consider how you might / if you need time to be tagged to your data.