If you are really advanced, you can also resize the image so that more of it fits in the 128x128 frame! A few years ago on certain forums, having silly photoshopped-out-the-arse signatures with effects and filters everywhere was popular, though I don't think it ever applied to avatars (thank god).
You can use either Paint.NET or GIMP to edit an image for avatar and signature creation (yes, they are both FREE to use). Though, it's best to find an image with high quality for best results. If you want transparency (like mine), make sure you clear out any unwanted parts of the image without harming the character. Then after that, save the image in .png format. Here's an example of Paint.NET.....
Make sure as Jarby said to properly resize and crop the image to get the best out of the avatar's quality (Maximum dimensions; width: 128 pixels, height: 128 pixels, file size: 88kB. Formats .jpg and .png supported)
"If you don't try, you won't learn. If you don't learn, you won't progress." *~ Universal Offset 0 User ~*
I used Adobe Illustrator + GIMP to make my avatar. If you just want a simple transparent one, then all you need is GIMP or Paint.NET like whymeman said.
Shapes, Vectors, Text : Adobe Illustrator (not free, if someone knows another program for this purpose please tell me!) Masking and Exporting: Adobe Photoshop (not free), GIMP (free), Paint.NET (free)
Obviously, Photoshop is recommended because it has great selection tools that make transparent avatars super easy to make.
Nothing else to say except crop as close to the edge of your avatar as possible, so you don't have to scale it down when you're finished. Also, don't compress the image at all. Any 128x128 picture exported from GIMP is less than the size limit for osu! (from what I've seen) so try to preserve the quality as much as possible.