Thanks for the answers everyone: from the links and methods seanb and some posted, I was able to come up with a solution which works for IE and Firefox, so I thought I'd post a 'complete' answer. Here it is as a handy jQuery extension!
The jQuery Extension
jQuery.extend({
    skype : function(failureFunction) {
        var $ = jQuery;
        if ($.browser.safari || $.browser.opera) {
            return true;
        } else if ($.browser.msie) {
            try {
                if (new ActiveXObject("Skype.Detection")) return true;
            } catch(e) { }
        } else {
            if (typeof(navigator.mimeTypes["application/x-skype"]) == "object") {
                return true;
            }
        }
        $('a[href^="skype:"]').click(function() {
            failureFunction();
            return false;
        });
        return false;
    }
});
Usage
HTML:
<a href="skype:your.skype.username?call">Call me</a>
<a href="skype:your.skype.username?add">Add me</a>
Javascript:
jQuery(function($) {
    $.skype(function() {
        // this function gets called if they don't have skype.
        alert("Looks like you don't have skype. Bummer.");
    });
});
And that's it!
If someone using Safari, Opera or Chrome comes along, it'll just let the browser deal with it.
edit: rejigged the function so that it only performs the check when the page loads, not each time the page is loaded. The $.skype function will now return a bool telling you if skype was detected or not.