The "right" solution is not always the "best" solution.
This is where ingenuity comes in.
cebebe's suggestion is the first step.
Afterwards, you WILL have a blurry, ugly image. He is correct in that you cannot gain the detail that would be obtained with a camera capable of shooting that image.
BUT you can make it look a little better.
The first, and clunkiest option is the Sharpen filter. It finds changes in hue and value and accentuates them. This sortof battles the blurry effect of interpolation. It's also hideous, don't use it.
But it also has a cousin, the Unsharp Mask. It basically works the same, but you can control some of the option, such as how much of the effect you want, and how much of a change in hue or value is necessary before applying the effect.
The problem is, this is still the same effect, and is still hideous, if less so.
But still useful.
You will want to use this effect to accentuate or suggest detail in the image, no actually change it.
So what you will do is create copies of the image into new layers (Layer->Copy Layer or something like that).
How many copies depends on how much time you want to spend. Let's start with 2.
Make sure these layers are on top of your original image layer, and adjust the transparency to something like 30% for both.
Apply the unsharp mask to both layers.
At this point, it's all up to you. You will need to play with three variables: Blend modes of the layer copies, degree of Unsharp Mask effect, and transparency level of the layer copy.
If you really want to get into the minute detail and nitty gritty, you can use more layers(6 or 9 if your image mode is RGB, 8 or 12 if your image mode is CMYK. also if your image is grayscale, 2 will suffice. If it is monotone (sepia?) you may want 4 or 6).
Basically you would have a Highlights and a Shadows (and maybe a midtones) layer for each channel.
Again I will reiterate, you will not get the detail to match the resolution, but you can fake it just a little. Sometimes, the effort is worth it, especially if it's an image you really need but cannot reproduce.