Supernovae (SNe) have been proposed to be the main production sites of dust grains in the Universe. Our knowledge on their importance to dust production is, however, limited by observationally poor constraints on the nature and amount of dust particles produced by individual SNe. In this paper, we present a spectrum covering optical through near-Infrared (NIR) light of the luminous Type IIn supernova (SN IIn) 2010jl around one and half years after the explosion. This unique data set reveals multiple signatures of newly formed dust particles. The NIR portion of the spectrum provides a rare example where thermal emission from newly formed hot dust grains is clearly detected. We determine the main population of the dust species to be carbon grains at a temperature of ~1,350 - 1,450K at this epoch. The mass of the dust grains is derived to be ~(7.5 - 8.5) x 10^{-4} Msun. Hydrogen emission lines show wavelength-dependent absorption, which provides a good estimate on the typical size of the newly formed dust grains (~0.1 micron, and most likely <~0.01 micron). We attribute the dust grains to have been formed in a dense cooling shell as a result of a strong SN-circumstellar media (CSM) interaction. The dust grains occupy ~10% of the emitting volume, suggesting an inhomogeneous, clumpy structure. The average CSM density is required to be >~3 x 10^{7} cm^{-3}, corresponding to a mass loss rate of >~0.02 Msun yr^{-1} (for a mass loss wind velocity of ~100 km s^{-1}). This strongly supports a scenario that SN 2010jl and probably other luminous SNe IIn are powered by strong interactions within very dense CSM, perhaps created by Luminous Blue Variable (LBV)-like eruptions within the last century before the explosion.