Microsoft have recently announced that Lync to Skype connectivity is now available. Meaning you can now send IM and make audio calls to Skype users (provided they are logged into Skype using their Microsoft account). Video calling is not yet available unfortunately.
This integration is achieve using your existing Lync to Windows Live PIC (Public IM Connectivity) federation, hence the requirement for the Skype user to be logged in with their Windows Live/Microsoft address.
Once you’ve added the user’s Windows Live/Microsoft address, you can IM them like this: