How to add an RSS logo to my blogs header?

You want some code to be added to the #title element. You can do this, as Sorich said, by copying the header.php file and just adding it there, but you could also try to add it in the footer and then using Javascript move it to the correct element. This might survive theme upgrades better, but is maybe not so user-friendly (the image appears just after the page has been loaded, giving a strange flash).

The code you need is simple, let’s take the example you gave:

<p>
    <a href="https://wordpress.stackexchange.com/questions/2742/<?php echo bloginfo("rss2_url'); ?>">
        <img style="vertical-align:middle" src="http://www.r-bloggers.com/wp-content/themes/black-lucas/images/rss.png" alt="Subscribe to R-bloggers">
        RSS Feed
    </a>
</p>

Of course, you would copy the image to your own server and change the path. You can check the styles used on the page, using a good web inspector/debugging tool (like Firebug).