Adding links to the side menus EXCEPT for Toolbox is easy: just edit the system message
Mediawiki:Sidebar.
http://www.mediawiki.org/wiki/Manual:Interface/Sidebar
Adding to the Toolbox: use the hook MonoBookTemplateToolboxEnd:
function toolbox(&$monobook) {
echo ("<li> <a href=\"%s\">%s</a></li>",
$yourlink,
$yourtext);
return true;
}
DanB