I've had this asked of me a few times but most recently on my AMA, so I decided to actually make a tutorial for those of you that care.
This is all done in Photoshop CS5.1 but should be able to be translated into any version of PS or GIMP, just the interface might be slightly different.
For my avatars i work at 184x184px so it's slightly larger than what the forum will display on either posts or in your profile, but not big enough that you get bad/weird compression on the forum end.
I'll try to explain was i can as if you've had no experience with Photoshop before instead of making the assumption that you know what you're doing.
Use the Ellipse Tool to create a circle on the canvas, colour does not matter. Don't make it edge-to-edge and Top-to-bottom, have it slightly smaller than the canvas and put it in one of the corners, this allows sufficient space to have the "overflow" details since you don't want them to be cutoff at the edge of the canvas
Find the image you want to work with. something with parts that extend out from the main focus; generally hair, horns, accessories, clothing etc.
For this tutorial I'm using this
mainly for the red feathers on her head and the little side ponytail she has.
Make sure the circle layer is below the focus image like this
you will then right click the focus image (in this case "Layer 10") and select "Create Clipping Mask"
what this does is constrain the focus imagine to the bounds of the layer below. since the ellipse is a vector layer, everything outside of the shape is transparent, making the focus image become the circle including the transparency around the outside
duplicate the focus image layer (either with ctrl+J or drag the layer onto the "new layer" button) which will make another layer above the current clipping mask
Now ctrl+click the circle vector layer (in the above imagine, the white circle, not the black colour box) to make a selection of the circle. Then right click inside the selection and select "Inverse Selection". you should see something like with with the "marching ants" both around the outside of the entire canvas and the circle
As you can see there are parts outside of the circle, this is what will become the "overflow"
Make sure you have the newest layer selected and start erasing the background leaving the "overflow" visible, you can go as far into the circle as you wish since we still have the clipping mask underneath, just worry about the outside. While her leg is also on the outside, i erase this too as I don't want the edges of the canvas to cut anything off. the border is the circle.
an easier method of erasing around the "overflow" is to use the pen tool to make the selection instead. that's a whole other tutorial on how to use that efficiently so it's not something i'll go into here.
You will eventually have something like this:
Now we add the borders. First ctrl+click the circle vector layer again to make our circle selection. Create a new layer onto of all the others and go to edit>stroke.
for the first border, change the size to 4px, colour to white and make sure it's location is "inside" not "center". click OK
then in the layer subwindow, change the blending from "normal" to "overlay". while the stroke window does have a blending section, this doesn't work with what we're trying to do.
this will give you a brighter border around the edge of the entire circle, we want to then erase the parts to overlap the overflow so it looks like the border is going behind these parts.
Now we add the black border. so again ctrl+click the circle vector layer to make our circle selection. Create a new layer onto of all the others and go to edit>stroke.
however this time we will change the size to 2px and the color to black
click OK again, erase the overlapping parts and you're done.
it's really quite simple, you can experiment with different images, even different base shapes, the process is exactly the same
Here's a few others i rushed through.
hopefully this helps for the people that care and got this far. It's my first time writing an actual tutorial so i hope it make sense and was easy to follow, if something seems skipped or unclear let me know and I'll update it as best i can.