The ideal size would differ from one browser to another, from one system to another.
Avoid making it too small or too large. A background image the size 1x1 may have rendering problems in some browsers. You should at least make it a few pixels in each dimension.
I remember that Netscape 4 refused to repeat images if they were less than something like ten pixels wide. Browsers today are less sensetive, but it still makes sense to not make the images too small.
The compression of images (at least for GIF and PNG images) are based on repetition, so if you make the image larger by repeating it, the extra image size will add very little to the file size.