We present a photometric survey of the stellar halo of the Andromeda galaxy, using Suprime-Cam on the Subaru Telescope. A detailed analysis of VI color-magnitude diagrams of the resolved stellar population is used to measure properties such as line-of-sight distance, surface brightness, metallicity, and age, and these are used to isolate and characterize different components of the M31 halo: (1) several substructures, and (2) the smooth halo. First, we study M31s halo substructure along the north-west/south-east minor axis out to R ~ 100 kpc and the south-west major axis region at R ~ 60 kpc. We confirm two substructures in the south-east halo reported by Ibata et al. (2007) and discover two overdense substructures in the north-west halo. We investigate the properties of these four substructures as well as other structures including the western shelf and find that differences in stellar populations among these systems, thereby suggesting each has a different origin. Our statistical analysis implies that the M31 halo as a whole may contain at least 16 substructures, each with a different origin. Second, we investigate the properties of an underlying, smooth and extended halo component out to R > 100 kpc. We find that the surface density of this smooth halo can be fitted to a Hernquist model of scale radius ~ 17 kpc or a power-law profile with ~ R^{-2.17 +/- 0.15}. In contrast to the relative smoothness of the halo density profile, its metallicity distribution appears to be spatially non-uniform with non-monotonic variations with radius, suggesting that the halo population has not had sufficient time to dynamically homogenize the accreted populations. Further implications for the formation of the M31 halo are discussed.