There's plug-ins for most image applications for doing this that will give you better results, Genuine Fractals is the most common one but it's $$$. It doesn't add detail however as that is impossible no matter what you see on TV.

What it does do is examine the images for contrasting edges and will keep them defined so you don't get the soft blurriness.
For a poor mans version you can use any decent image editing application and scale the image in steps using bi-cubic as the method. In between each step use a noise filter program like neat image. Neat image will remove the softness and sharpen the edges, end result is pretty sharp image closely comparable to the $$$ scaling plug-ins.
Small images like the Avatars are really tough under any circumstances.