If the phone has a built in modem I understand it is pretty easy using a data cable and the AT commands - do a google and you should be able to find a Nokia AT command document.

One Issue I can see is that some of the new phones only use USB for comms, and as a PIC cannot act as a USB Host device you will need to use a serial interface to the phone.

Bill.