Check voltage at comm-pins on your nokia (the internal 'dots') to verify that they are almost TTL-level
(0V ..3.5V ?) If this is the case, you can connect directly. (add a small resistors i series with arduinos TX)
I guess softwareserial can be used. Connect common groud,
Rx to Tx, both directions.