no worries, well the links at the bottom of the pages i.e on the theme are easy and can be changed by a simple edit to the footer however changing these files will require a bit of coding understanding and if a new theme version is released you will have to make the changes to the new theme so the recommendation would be to create a child theme and make the edits on the child rather than the source theme files (makes life very easy when upgrade is due).
A search on child theme/s on the forums will bring back lots of topics and info how to create them.
The following is from memory so may not be correct on the latest CP release code lines may have changed and with any site changes make sure you backup first of all!
From the wordpress backend look for Appearance > Editor and click on Footer (footer.php)
Scroll to the bottom and look for the following:
<p>© <?php echo date_i18n('Y'); ?> <?php bloginfo('name'); ?>. <?php _e( 'All Rights Reserved.', APP_TD ); ?></p>
<?php if ( get_option('cp_twitter_username') ) : ?>
<a href="http://twitter.com/<?php echo get_option('cp_twitter_username'); ?>" target="_blank"><img src="<?php bloginfo('template_url'); ?>/images/twitter_bot.gif" width="42" height="50" alt="Twitter" class="twit" /></a>
<?php endif; ?>
<p><a target="_blank" href="http://www.appthemes.com/themes/classipress/" title="Classified Ads Software"><?php _e( 'Classified Ads Software', APP_TD ); ?></a> | <?php _e( 'Powered by', APP_TD ); ?> <a target="_blank" href="http://wordpress.org/" title="WordPress">WordPress</a></p>
You can either comment out the code, remove the code line or replace with your own but remember you can't claim to own or have created the classified software so i recommend replacing with just a copyright all rights reserved etc..
Save the changes and refresh the front end to see the change.
With regards to the links in the source code i am not sure if you can edit this or not it depends on the CP licensing perhaps a mod can answer on that but in general i think you will find you cant remove the headers as thats part of the licensing, could be wrong..
Lastly if you want to add some branding to the backend there are plenty of plugins available like the one you mention from WPMU DEV i have used that and it works great, also white label branding for wordpress
again a plugin you have to purchase but works well.
I think what should help you