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:
That setting controls apps' ability to use this API, which includes Google's apps such as Market.