The Co-59-NMR on single crystals of LaCoO3 has been studied in order to investigate the spin-stale transition through the nuclear-spin relaxation in this compound. Below T similar to 35 K, the spin-lattice and spin-spin relaxation rates show a thermal-activation-type temperature dependence with an energy gap of similar to 180 K. This value is close to the energy difference between the low spin state (S=0) and the intermediate spin state (S=1) predicted in the two-stage spin-state transition model with the intermediate spin state. The apparent spin-spin relaxation rates depend on the resonance peaks split due to the nuclear-electric-quadrupole interaction, which is explained by an indirect nuclear spin-spin interaction through the interacting paramagnetic electron spins. This observation is consistent with the ferromagnetic short-range correlation among the electron spins on Co3+ ions confirmed by neutron-scattering experiments.