The logo can be in jpg format as well. I'm not sure about png.

If you use a different format, just indicate it in includes/languages/english/YOUR_TEMPLATE/header.php.

Code:
define('HEADER_LOGO_IMAGE', 'logo.jpg');
You can find out the size with an image editor like Photoshop or Paint Shop Pro.