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