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 !