There are many techniques to do this. One very simple one that I often use in practice is to use many colors on a similar palette and just generally paint them using the brush tool all over the place. It looks incredibly bad at first, until you apply the Filter→Blur→Gaussian Blur to taste.
The end results is a very simple, diffused, gradient-like, background. This is also accomplished in Adobe Illustrator through gradient meshes, but is a more complicated and precise process.
Note: If you're wondering how the edges were not blurred, I contained them with an unlinked layer mask that was not affected by the blur.