This really depends on the template you are using, but generally, you can change the logo graphic by editing the main_page.tpl.php file in whatever template's directory you are using.

For example, in the default osCmax fallback template, depending on the version you want to find the below lines and then change the image name to your custom image name.

Version 2.0RC3 this is called:

'oscmax.gif', 'osCMax v2.0 - Power E-Commerce'

Version 2.0.4 and more current (v2.0.25, v2.5) this is called:

'store_logo.gif', STORE_NAME

Change the name of the image above to match your new logo. Then make sure you have uploaded your new image to the /images/ directory of your store.