I'll be right round with my Soldering Iron...sheesh...
First off, you will need the schematic for the Nokia socket...what pin is data etc. Then you will need an interface design. Also look up Hayes compatible command set on the net, and that will tell you what each AT command is and does etc, your phone will no doubt only support a subset of those commands.
A good listing of the AT commands will also give you the equivalent character strings to send...
After that you will need to write your code for the micro to output those strings, in the order you need to achieve what you want to achieve, you will also have to receive them as well for anything meaningful to be conveyed.
Do a google search for GSM modem projects, that may turn up something you can use for background information, like wiring to the Nokia spec etc
I wouldn't even consider C to write this personally...