How can I transfer messages from iPhone 4 to iPhone 5? How can I transfer my messages from an iPhone 4 to the new iPhone 5 that has a different sim card?
You can backup to iCloud, and then restore to your new phone. This will ensure that not only just your messages but all your data will be transferred over to your iPhone 5.

Here is a very helpful article on using iCloud for backup and restore.
http://support.apple.com/kb/ht4859