Transfer SMS messages from Android to new Android phone
SMS Backup &amp; Restore (free and highly rated) in Market seems like a good fit for the task.  Backs up SMS to gmail (threaded), supports restore to SMS (hence the name).