I think they can be any common image format. At the very least, you can use PNG, JPG and GIF (including animated GIFs).
Also, the size is not limited to 36x36. You can have smaller or larger icons (although I'm not sure what the limit is. At some point the site would just scale your image automatically).
___________________
Try to take over the world!
