Adding an image would be easy and you could add it inside header.php file right above or below this code:
<?php sparkling_featured_slider(); ?>
<?php sparkling_call_for_action(); ?>
A simple image tag would be enough for that task
<img src="patch-to-image/smiley.gif" alt="Smiley face">
But to make it appear only for first time visitors you need some more advanced coding ass you need to drop cookies to that user, so next time this message won’t be visible. It is doable but you need to master PHP to get this done.
An easier alternative would be to use some read-made visitor welcome plugin that already have cookie functionality built in and you would have edit HTML/CSS part to make it look like in screenshot posted above.