The logo is stored under: /[THEME_PATH]/images/logo.jpg, you can replace that file (make sure the dimension is same as the existing one)

If you want to use GIFor PNG logo, you can upload the logo to any path you like, then edit 2 files:

1. /[THEME_PATH]/nas_bar_cust.php (Main logo in the header):
   <div id="logo"><a href="/store/index.php" title=""><img border="0" alt="" src="/store/images/logo.jpg"></a></div>
2. /[THEME_PATH]/nas_contacts.php (logo in the Contact Us page):
   <img class="img_border" alt="" src="/store/logo.gif" border=0><p>