Update:
Read the Docs for your version of Django. e.g.
https://docs.djangoproject.com/en/1.11/ref/contrib/admin/#admin-overriding-templates
https://docs.djangoproject.com/en/2.0/ref/contrib/admin/#admin-overriding-templates
https://docs.djangoproject.com/en/3.0/ref/contrib/admin/#admin-overriding-templates
Original answer from 2011:
I had the same issue about a year and a half ago and I found a nice template loader on djangosnippets.org that makes this easy. It allows you to extend a template in a specific app, giving you the ability to create your own admin/index.html that extends the admin/index.html template from the admin app. Like this:
{% extends "admin:admin/index.html" %}
{% block sidebar %}
{{block.super}}
<div>
<h1>Extra links</h1>
<a href="/admin/extra/">My extra link</a>
</div>
{% endblock %}
I’ve given a full example on how to use this template loader in a blog post on my website.