Probablistic interpretation of entropy After taking a statistical mechanics course, I'm somewhat surprised that my intuitive highschool understanding of entropy doesn't match my current understanding. 
When I was introduced to entropy, I was told that it (and the second law of thermodynamics) is just a statement that things move probabilistically toward their most likely state. I remember an example given with atoms, how entropy being defined (for atoms) as dq/T makes sense from this perspective.
But now in graduate school I'm told that entropy is the expected value of "information," that it's the log(Z), that it's always increasing, AND that it is dq/T.
I've had a really hard time trying to really connect all these facts mathematically. 
I've read a little bit on wikipedia about H-theorem, and tried to piece together an understanding of entropy but I'm still left with quite a few questions:
If entropy can be explained probabilistically, does that mean we can describe a system's entropy as a random variable? Can we find the probability a given system changes entropy as a function of time (microcanonically, canonically, or whatever)? And if we did this, could we show more explicitly how entropy is always increasing at large timescales?
Can we derive the first law of thermodynamics using microscopic arguments?
In stat mech, we always calculate the partition function, and then just assume that the first law (or maxwell relations) holds - and then just plug-and-chug. But I always imagined a more statistical argument taking place.
I've seen entropy talked about so casually; whether it's the heat death of the universe, or violation of laws of thermodynamics - that I really wish I was more comfortable with the logic behind going from microstates to macrostates.
 A: 
If entropy can be explained probabilistically, does that mean we can describe a system's entropy as a random variable?

No, it does not. Thermodynamic entropy can be given additional explanation in probabilistic terms applied to mechanics, but it is still thermodynamic entropy - a function of macroscopic variables like internal energy, volume, number of particles, which do not fluctuate. What fluctuates are the mechanical quantities that are described in probabilistic terms.

Can we find the probability a given system changes entropy as a function of time (microcanonically, canonically, or whatever)?

If the system undergoes thermodynamically reversible process,  change of its entropy can be in principle calculated via $\int dQ/T$, no probabilities needed.
If the process is not reversible, there is no thermodynamic entropy.
There are more notions of entropy - thermodynamic entropy, information entropy, coarse-grained entropy...

And if we did this, could we show more explicitly how entropy is always increasing at large timescales?

Thermodynamic entropy is not something that increases with time; it is not defined as a function of time, but as a function of equilibrium state.
What can be said based on the 2nd law of thermodynamics is that if  the system undergoes any adiabatic process that takes it from equilibrium state 1 to equilibrium state 2, the entropy of the state 2 in not lower than the entropy of the state 1:
$$
S(2) \geq S(1).
$$
There is no time and no continuous increasing involved.
A: I took a quantum statistical mechanics course as an undergraduate using  Kittel's book
"Thermal Physics"s this made sense to me because he used simple models.  In graduate school
we used Landau and Liftshitz book which was confusing.  My understanding of the ideas was that Bolzman made an identification of classical thermodynamic quantities Temperature, Entropy and more with statistical quantities.  It was more of a one to one corespondence than a logical deduction.  Boltzman was so pleased with his discovery that he had 
   S=Log (probability) or something like it as the only thing on his tombstone, he later commited suicide, so its best not worry about this too much.
