Create the Background
Create a new document the size of the final piece and fill the bottom layer with a background to work on top of. Having a background saves you from the need to fill every space in the image and avoids ugly gaps.
You can make a background in a number of ways. One technique is to use an enlarged photo, such as a flower or a texture, to fill the space (see Figure 3). If the image is too small, paste it multiple times into multiple layers and overlap them to fill the space. Use a soft or textured brush to erase the hard edges and blend the layers.
Figure 3 One option for a background is to use a texture or other photo and stretch it to fit.
You can paint a background by filling the background layer with a solid color and painting over it with textured brushes and different colors. Keep your colors close to the palette of colors in the images you will use. Sample colors from a photo using the Eyedropper tool and use them to paint with.
You can also fill the background with a gradient by clicking the Gradient tool, choosing the gradient colors and style, and dragging to fill the background with the gradient (see Figure 4).
The Difference Clouds filter also makes a good background. Fill the image with a color and choose Filter > Render > Difference Clouds. Then choose Edit > Fade Difference Clouds and vary the opacity and blend mode until you have an attractive result.
Figure 4 A gradient fill makes a good starting point for a collage background.