If you check wordpress you'll see the get_links() function has been deprecated. So I won't use that function for an answer.
http://codex.wordpress.org/Template_Tags/get_links
The new function that should be used is wp_list_bookmarks.
http://codex.wordpress.org/Template_...list_bookmarks
The default call
<?php wp_list_bookmarks(); ?>
will have Bookmarks divided into Categories with a Category name heading, just like you want.