Microsoft have now announced that video is now available. Currently only available on the Skype Windows Desktop client (and you need version 7.0.x.100 or later) you can now do video to video calls.
Although limited to Skype for Windows Desktop, the Lync end point can be on any OS, I've personally tested this on Windows, Mac OSX, iOS and Android.
First things first. Make sure your Skype for Windows client is up to date.
Establishing a Video Call is easy - right-click the federated Skype contact and click "Start a Video Call"
Establishing a Video Call
Call between Skype and Lync (Windows)
Skype (Windows) and Lync for Mac 2011
Video Request on Lync Mobile client
Video Call on Lync Mobile (iOS) with Skype (Windows)
Now, while a number of devices will say "Video Capable" unless you run the Skype for Windows client, video will ultimately fail.
Can't wait for the other Skype clients to catch up!