1. create a Skin. See How To Create ASkin.
2. declare your skin in the preferences page by specifying the full name of the wiki page of your skin (XWiki.MySkin for example).
3. attach a 150x40 logo to your skin page (call it mylogo.jpg for example)
4. add the following code in the styles.css field of your skin (use "Edit Object" to access the field):

@import "xwiki.css";
@import "wiki.css";
@import "page.css";
@import "rss.css";

#xwikilogo img {
 background-image: url("mylogo.jpg");
}

It is important that the logo is 150x40 otherwise it won't fit in the space. If you need a bigger logo, you will need to override the header.vm template. See How To Create ASkin.

That should be enough to change the logo