Easy to do in InDesign, but not so much in Illustrator. It’ll probably be in CS6 (though I’ve been thinking that for quite a few versions now)
Anyhow, it actually is pretty easy to do in Illustrator, just not as straight forward. You need to use the power of the appearance panel (which you can read more about here, here and here) and you won’t technically be putting a gradient on a stroke so much as you’ll be making a fill behave as a stroke and giving that fill a gradient fill. Yeap.
So we take a basic rectangle shape to start with.
I made an object with a dark green fill and no stroke, placed over a red background shape.
Now, with your object selected, go to the flyout menu of the appearance panel, “Add New Fill” This will become our stroke.
Right now, all that we have is two overlapping fills, exactly the same. Select the lower one by clicking on it in the appearance panel. With the lower fill selected, go up to your Effects menu and go to Effect->Path->Offset Path… The distance you choose is how far out it will offset your path so choose a distance that is half of what you wanted your stroke width to be. (since your stroke would normally straddle the bounds of your object) You should be looking at something like this:
All that’s left now is to color the fill that you offset with a gradient. With that fill still selected in the appearance panel, make it a gradient by choosing a gradient out of the swatches, clicking on the gradient swatch in the gradient panel or by using the gradient tool (if you’re on cs4 or above)
Note that the “stroke” is left blank. The only thing extending beyond the bounds of our object is our offset fill. This trick can be applied to any other object, including text.
(on this, I also put an inner glow on the main fill to cut it out of the offset fill)