Skype on OS X (and on Windows, for that matter) does not provide a way to save video messages. From what I understand, you’ll need to pay for a pro version of Skype (according to what I’ve read in forums; it’s not something I’ve confirmed with Skype.com) for the ability to save video messages. That sounds ridiculous to me. There’s another way. I provide the simplest solution here.
There’s now a free and open-source way to securely encrypt calls on iPhone, and its cross compatible with Android callers too. It’s easy to install, and easy to use. Free txt messaging is on the way too. Check it out.