power of 2 = 2^n (where n = 0 … 10)
I.e. the width and height should be one of 1,2,4,8,16,32,64,128,256,512,1024.
The texture does not need to be square.
Some samples for valid texture sizes:
128x128, 256x64, 128x1
This “power of 2” restriction is due to the so-called mipmapping of the textures (if you are interested, google for “texture filtering” or something like that).
Remark/Warning: Altough 128x1 or even 1x1 are perfectly valid texture sizes (suitable for mipmapping), you should not choose dimensions below 4x4. I know of some strange bugs for such small texture sizes in combination with ATI graphics drivers.