Currently there is no way of reclaiming space occupied by background images. So if you upload a background image, don't like it, upload another, repeat and so on the available space for the site reduces every time you upload a background image. Whether the old images are actually retained or whether the storage counter is not reset is not clear but the fact remains that every upload of a background image will count against your storage limit.
Update Dec 2013: unfortunately this workaround no longer works
Unfortunately, some templates have been created with this issue.
- Go to Manage site > Site Layout
- If you don't have a sidebar, add one (you can remove it again later)
- If your sidebar does not have a Text box, add one
- Edit your text box
- Insert > Image
- Now you'll see all the background images that have been uploaded in the past. Google sites changes the image's name on upload. Find the name used by right clicking on an image and opening it in a new tab/window. The stored image name is everything after the last '/', eg '24b8d1c6bd1c64ab.png'.
- Create a small (1x1 pixel) image exactly the same name as the stored image name (it is case sensitive).
- Upload this image to the sidebar text box and it will overwrite over the previous background image. Save everything as it is now.
- Repeat as many times as necessary
- Remove any extraneous text boxes, sidebars as necessary