Did you actually delete the message, or just archive it? If you were viewing the message and just hit the X, the message would have been archived and is retrievable. But, if you selected the message and went to "actions-->delete conversation" it's gone forever.
If you did just archive the message you can go to your inbox and click "other-->archived" and it'll show your archived messages. If you fully deleted the message though, Facebook doesn't offer any recovery support to get it back.
All the best.