Well, just about everyone. The feature is available on essentially every platform (Windows desktop, Mac, iPhone, iPad, iPod, Android, BlackBerry) except Windows Phone, which seems a little odd considering the fact that Microsoft acquired Skype for $8.5 billion in 2011.
The feature was first announced as beta back in February with a limit on the number of sent messages allowed (this was unlimited for premium Skype subscribers). Now, there is no cap on messages sent regardless of whether you pay for the premium service.
Here’s a quick tutorial on recording and sending video messages on Skype: