Theres nothing fancy going on there, the outline is just the original sprite, coloured black, and jittered around by the outline width. This one has an outline 4 pixels thick which is about right I think, and needs about 16 jitters to get good quality results. Thats a few more jitters than I thought would be needed, but less than that tends to make the outlines look 'blobby' and uneven. 16 times overdraw doesn't sound too great, but it should only be on a fraction of the screen at a time so it shouldn't be a problem.
One neat twist to this is placing all the outlines on the same layer, behind the coloured versions. This means that when sprites overlap the colours run into each other, and the outlines merge on the outside edge, something like this:
I'm not entirely sure what I'm going to do with this effect, but for the amount of effort it requires it produces quite nice results. I think I'll end up using it on all my 'dynamic' sprites (ie. the player and other creatures) and leave the background tiles and others to be rendered as normal. Most background sprites don't change position so they can have the outline drawn in directly in the first place.