Hmm, ok now, this goes for two gray bars at the bottom of your image.
You can change this by editing
templates\xhtml\box\footer.tpl
The first, lighter line, contains top level categories, and you can add new links only before or after existing categories.
For example, if you want to add some link before categories:
Code:
<vte:box module="box_sections">
<vte:params>
<vte:param name="id" value="0" />
</vte:params>
<vte:template>
<ul>
<li><a href="YOUR LINK">YOUR LINK TEXT HERE</a></li>
<vte:foreach item = "category" from = "{categories}">
<vte:if test="{category.view_subcat}">
<li>
<a href="{category.get_href}">
<vte:value select="{category.category_name}" />
</a>
</li>
</vte:if>
</vte:foreach>
</ul>
</vte:template>
</vte:box>
As for the second, darker line, that is just static HTML and can be customized easily.
Links that are inside darker bar, are contained within
<div class="static_footer"> block.