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 GIF or 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.gif"></a></div>