TheSpecialist is wrong - evaluating the navbar before the page is completely built can have unpredictable effects. There's a
reason it's evaluated last.
I did this for Wizards of the Coast. It can be done entirely from the templates themselves, but it does require the editting of more than a few templates. A navbar on the bottom though is only likely to be especially useful for the FORUMDISPLAY and SHOWTHREAD templates. The process is the same regardless of the template you're editting.
Find the $footer variable in the template. Above it add this code
PHP Code:
<table cellpadding="0" cellspacing="0" border="0">
<tr valign="bottom">
<td><a href="#" onclick="history.back(1)"><img src="$stylevar[imgdir_misc]/navbits_start.gif" alt="$vbphrase[go_back]" border="0" /></a></td>
<td> </td>
<td width="100%"><span class="navbar"><a href="$vboptions[forumhome].php?$session[sessionurl]">$vboptions[bbtitle]</a></span> $navbits[breadcrumb]</td>
</tr>
<tr>
<td class="navbar" style="font-size:10pt; padding-top:1px" colspan="3"><a href="$scriptpath"><img class="inlineimg" src="$stylevar[imgdir_misc]/navbits_finallink.gif" alt="$vbphrase[reload_this_page]" border="0" /></a> <strong>$navbits[lastelement]</strong></td>
</tr>
</table>
Now you'll probably want to adjust that code to suit your tastes and whatever style set you're using - but that's the basics.
Note that all this applies only to the breadcrumbs. The rest of the navbar can be placed pretty much whereever you please. Personally I pulled the dropdowns of the navbar and stuck them in the header.