The way to understand the relation between the two definitions is to consider two systems which are touching, so that they exchange energy. The energy exchanged is called "heat" when it is random and microscopic.
Start with the definition in terms of microstates. The entropy is the log of the number of microstates, so there is an $S_1(E)$ for system one, and $S_2(E)$ for system 2. The total number of microstates is the product of the number of states in each of system 1 and 2, so you get that the logarithm is additive
$$ S(E) = S_1(E_1) + S_2(E-E_1)$$
Now you ask, what is the condition that $S(E)$ is at a maximum? This determines when you reach equilibrium. The condition is that
$$ {\partial S \over \partial E_1} = 0 = S'(E_1) - S'(E-E_1)$$
So that the equilibrium condition is that the derivative of the entropy with respect to the energy of the two systems must be equal.
We define the thermodynamic temperature to be the reciprocal of this derivative, and one concludes that two systems are at the same temperature, and so in thermal equilibrium, when the rate of increase of entropy with energy is equal for the two.
Then you ask, what is the change in entropy in a system when you add a quantity of energy dQ to the system? By the definition of the derivative, it is
$$ {\partial S\over \partial E} dQ = {dQ\over T} $$
There is nothing more to it then that. The issue is to make sure that the thermodynamic concept is identical to the intuitive concept of temperature, and for this it helps to verify that for an ideal gas, the thermodynamic temperature is (up to a universal constant) the product of the pressure and volume divided by the number of particles in the gas. To verify this, you can just count the microstates, and differentiate.