Difficult to say but it should be near the intended screen resolution of the website itself. Popular is around 1000px in width or 1024x768.
If you can design or blend the borders of the background according to the background colour it should look nice in every screen resolution including and above the minimum your aiming for.
Here's a windows bg I made at various popular screen resolutions, might help.
preview here http://gcmax.deviantart.com/#/d3ftgys