Since Emacs 24.1, Emacs runs kill-emacs which runs the functions in kill-emacs-hook. So the question, and the rest of this answer, are only relevant to older versions.
The right place to run something before Emacs shuts down is either kill-emacs-query-function if you want to be able to cancel the shutdown or kill-emacs-hook if you don't. The problem you're facing is that your OS does not notify Emacs to shut down gracefully in a way that Emacs understands, or to look at it the other way, Emacs does not understand your OS's request to suht down gracefully.
A graceful way of shutting down Emacs 23 from the outside is to run emacsclient -n -e '(kill-emacs)'. That's obviously not a generic way of telling a program to shut down gracefully.
The normal way to shut down a process gracefully on unix is to send it a SIGHUP or SIGTERM signal. Unfortunately, Emacs treats almost all signals as fatal, and only runs an emergency auto save and no lisp code when it receives them. This is not configurable from lisp. A different behavior has been requested, but turned down.
A partial workaround (found here) is to run session saving hooks in delete-frame-functions. This hook is likely to be run before the system shutdown sequence, either when you close your last frame or when the X server dies (taking your terminals with them if you run Emacs in a terminal). Make sure you don't run the hook that kills the server in delete-frame-functions.
By the way, if you were going to use this exact hook, note that your code is a complicated way of writing (add-hook 'server-done-hook 'savehist-save), and that's not useful since there's already savehist-autosave in kill-emacs-hook.
