You might want to take a look at SMS Backup and Restore apps on the playstore. An example app would be SMS Backup & Restore, which allows you to backup the SMS from your device and restore it later. As it backs up to XML, you could backup on your old device, transfer the backup XML file to the new device, and restore it there.
As the screenshots show, this should be easy to do: From the settings, you define where to store your backups on the sd card, so you know where to find them. After having done the backup on your old device, connect it to your PC and copy that folder to your PC. Then connect the new device, copy the folder to it, disconnect the device, and run the app to restore the backup. Et voila: your messages are transfered.
Side effect: Keep the app, and have it creating backups from time to time. So in case you need to factory reset your device one day, that's one piece of data you already took care for not to lose ;)
Note: That's just one of the many possibilities. Depending on the OS running on your PC, it probably could be done with MyPhoneExplorer as well (so you have some more features) when running Windows. But there are also a lot more suitable apps on the playstore -- simply search it for sms backup.
If the "old phone" is not running Android, it gets a bit more difficult -- but not impossible, it seems. The playstore also lists some migration tools like e.g. the SPB Migration Tool, which promises:
SPB Migration Tool provides phone data migration to Android from Windows Mobile and Symbian platforms and comes with a complete solution, which allows copying the call history, text messages, contacts and bookmarks.
With ~7 EUR it's quite a bit expensive compared to others. If you only care about your SMS, SMS Migrator might offer an alternative: about 2,50 EUR, but ratings look a bit mixed. So for messages only, I rather recommend to take a look at Phone Copier:
It provides a complete phonebook and messages copy from almost any phone to your Android or from Android to any other phone.
You find a demo video on the Playstore page of the app. Hm, if I remember correctly, this tool was even written by an Android Enthusiast -- I wonder if he missed this question ;)