For the Data Frame Properties on a map in ArcMap, what is the difference between selecting a new coordinate system and using a Transformation?
A transformation should be used to "transform" between two systems such as geographic coordinate system (GCS) and Projected Coordinate System (PCS). There are other instances for it's use also. Link #3 is the ESRI 9.3 help page that is pretty good about describing the difference.
Any Projected Coordinate System has a Datum. If you are converting in between two different Coordinate systems, with different datums, you will need to use a transformation.
If the two coordinate systems are based on the same Datum, then a datum transformation is not needed.
In the ArcGIS world, a 'projection' converts between a geographic coordinate system (GCS) and a projected coordinate system (PCS). A geographic transformation, aka datum transformation, aka transformation, converts between two geographic coordinate systems.
When you set the data frame's coordinate system, you are defining the coordinate system (including the unit of measure) that you'll be working in. Any layers that are in a different coordinate system will be automatically projected (or 'unprojected') to this coordinate system. If a layer's coordinate system uses a different GCS, then you may see a warning that they're different. Whether you see the warning or not, you should decide whether you need to set a geographic transformation. Neglecting to do so when it's necessary can lead to data being up to a few hundred meters offset.
ArcMap only sets one automatically: NAD_1927_To_NAD_1983_NADCON, which transforms between NAD27 and NAD83 in the lower 48 states.
Std Disclaimer: I work for Esri.