On an Android phone the wallpaper spans across all of the home screens.
So what size should pictures be to fit properly as custom wallpapers?
Here are the correct wallpaper dimensions for the phones cited in Leimi's answer:
If you device isn't listed there is an easy way to figure out the dimensions of the wallpaper based on your particular phones resolution:
so for example my Moto Droid has a screen resolution of 480x854 so I want my wallpaper to be 2x the width (480 pixels) and 1x the height (854 pixels) = 960x854.
Here is a chart with most devices specs to help find the resolution.
Also check out this Lifehacker article that explains Android wallpaper sizing well.
It depends on your screen resolution :
edit : in fact some of this dimensions work but are not the correct ones (they fit because of the same aspect ratio). Matt's answer is better !
I think you shouldnt look at resolutions, but aspect ratio.
Resolutions are device-specific, but all devices, regarding their screen resolution use the same aspect ratio for scrollable wallpaper.
As I recall, the ratio is 5:4, because this aspect is good for having a wallpaper that scrolls a bit while you scroll through your homescreens.
Its been a while since I got that info so something might have changed, but as long as you keep that ratio (and the resolution higher than your devices resolution) you will have a nice crispy-clear image.