You need to tell us what image type your are saving it as, this is probably the root of the problem. Secondly, how much did you compress it. And thirdly how large is the image / what are you using it for. If it is for a background, what you should do is create a new document in photoshop (say 800×800, the most important value is the height, dpi you can leave at 72). Go ahead and create your gradient until you are happy with the result. Then crop the image width to 1px but leave the height the same. Save for the web as a jpg, but leave the quality at 100. Then use the css property repeat-x and you will have a nice gradient.
This will only work for linear gradients, a radial you will have to use a full size image.
Just post a screen capture and we can help you better.
This is just a tricky subject in general. It’s funny how the more subtle the gradient to more susceptible to banding it is and ultimately the less subtle. And this happens in Photoshop at full resolution and millions of color, not even just when saving with a limited color palette. The solution is often to change the tone of the two colors a little. As in, super dark grey to dark grey is going to be harder than super dark grey to dark slightly-reddish gray. Also, instead of just fading between two colors, you can add a bunch of intermediary colors in the gradient to help things along.