If you're using PHP, then a PHP include gets my vote. Search engines will handle this just fine as PHP is server side scripting.. so by the time the search engine views the page the include has already been made.

1) create a page - footer.php
2) put your footer content in there, and nothing else.
3) remove any existing footer information from other pages on your site and replace with :
And you're laughing. Only need to update footer.php in future to make site-wide changes.

This method also works well for headers and menus and basically anything else you want to be uniform throughout the entire site.