You will probably want to use this function in footer.php
http://codex.wordpress.org/Template_Tags/wp_list_categories
Then style it with adding stuff to your style.css
file in your theme folder.
<?php wp_list_categories('title_li=&show_count=1'); ?>
is the basic code to go in footer.php. You will probably need to wrap it like:
<div class="footerCats">
<h5>Categories</h5>
<ul>
<?php wp_list_categories('title_li=&show_count=1'); ?>
</ul>
</div>
and then in style.css you can style .footerCats along with .footerCats ul, etc