I'm Running 2.3 Gingerbread. There is a setting Settings->Privacy Settings->Back up my data
If checked, what data does this back up? Where is it backed up? How do I restore it?
This setting backs your data up to Google's magic cloud. It includes what apps you have installed, and some apps' settings (if they are written to take advantage of it) which are restored when you first sign in to a new phone.
Relevant quote from the Android 2.3 user guide, pg 18:
You can choose to back up some of your data, such as your bookmarks, your user dictionary, your Wi-Fi passwords, and many other settings, to your Google Account, on Google servers. Some third-party applications may also take advantage of this feature. That way, when you need to replace your phone (when you upgrade or replace a lost phone), or if you reinstall an application, you can restore your settings and other data. For information about changing this setting later, see “Privacy settings” on page 370.
That setting controls apps' ability to use this API, which includes Google's apps such as Market.