I second SMS Backup+. It's one of the first app that I always install.
Incoming SMSes are backed-up almost immediately to the cloud (your Gmail account). You can access the SMSes from anywhere like it was an email. There is also a restore function, although I have never tried it. Especially useful when an iPhone user (my wife) sends me a contact, but I can't directly import it on my phone (encoding problem?). So I just go to Gmail, and import it from there.
If you have multi-SIM, you can even consolidate your SMSes from different devices to the same account.