Already available in preview form for Mac, iOS and Android, many can now use Skype Video Messaging using the Windows desktop client (for Windows 7 or above). Skype for Windows 8 will add the feature soon, as will Skype for Windows Phone. The last two can receive and view messages, but not record them.
To get the feature, Windows users will have to download the latest beta version of the Skype client. This will include the functionality, but may not be as stable as the regular official release in other areas. It runs on Flash, so that will be required to use the feature. Also, as Skype says: "The beta version of Skype for Windows desktop with Video Messaging in preview may not be available in all markets", you might find that you can't get it working just yet.
A number of other fixes have accompanied the Video Messaging feature on this beta release (6.5), including the issue where the ability to call is disabled in some situations, and the stability of the software to call when no camera is present.
As it is still in its testing phase, Skype is asking for feedback on the feature. Why not send it to them in video form?