How do I get back deleted messages?

If you did not back up or sync after you deleted the messages, restore from your latest backup. But all data will be set back to that point in time.

Sorry, but that only works if your iPod is backed up regularly. If you don't, your messages are gone.