Well,
You can use the default Graphene footer section to add four widgets. These will be located at the very bottom of your content area, just ABOVE the footer area on every page. Then, in each widget, you can add a list of custom html links.
Or, if you want to completely rebuild your footer, you can do that as well. It will give you something like on my site here:
http://www.plugins.joshlobe.com
Note, this isn’t using Graphene… but you can still achieve the same affect.
Lemme know which way you want to go.