Two-dimensional steady-state laminar natural convection of power-law fluids in square enclosures with differentially heated horizontal walls (heated from below) subjected to constant wall temperature (CWT) and constant wall heat flux (CHWF) boundary conditions has been analyzed in detail based on computational simulations and a detailed scaling analysis. The effects of power-law exponent n ranging from 0.6 to 1.8 on the thermal transport have been investigated for nominal values of Rayleigh number in the range 10(3)-10(5) and a Prandtl number range of 10-10(5). It is found that the mean Nusselt number (Nu) over bar increases with increasing (decreasing) values of Rayleigh number (power-law exponent) for both CWT and CWHF configurations because of the strengthening of convective transport. In contrast, the mean Nusselt number (Nu) over bar remains insensitive to changes in Prandtl number Pr in the range 10-10(5). It has been found that the (Nu) over bar values for the CWHF configuration remain smaller than the corresponding values in the case of CWT boundary condition (bc) for shear-thinning fluids, whereas (Nu) over bar in the CWHF configuration for large values of n remains greater than the corresponding values in the case of CWT bc (for identical values of the power-law exponent and nominal Rayleigh and Prandtl numbers). We find that the steady two-dimensional convection in this configuration is realized in a narrower parameter range in the CWT bc than in the CWHF bc. Underpinned by a scaling analysis, new correlations have been proposed for the mean Nusselt number (Nu) over bar for both CWT and CWHF boundary conditions and these correlations are shown to capture the computational results satisfactorily for the entire range of power-law exponents and nominal Rayleigh and Prandtl numbers considered here.