You need to read this paper by Jaynes. I can't explain it as well as him, but I will try to summarise the main points below.
The first thing is to realise that the entropy is observer-dependent: it depends on what information you have access to about the system. A finite temperature means that you don't have access to all the information about the state of the system; in particular, you cannot keep track of the (infinite) degrees of freedom of the bath. However, suppose that some demon could keep track of all the degrees of freedom of the system and bath: he/she sees zero entropy. For the demon, it looks a bit like the total system is at zero temperature (although really it is better to say that temperature is ill-defined for the demon).
Given that you are ignorant (sorry, but at least I'm not calling you a demon), you need to find a consistent prescription for assigning probabilities to the different microstates. The prescription must be 'honest' about what you do or don't know. The entropy is in some sense a unique measure of ignorance, as proved by Shannon. Therefore you should 'maximise your ignorance', subject to the constraint that you do know certain macroscopic observables, e.g. average energy or average particle number if the system is open, etc.
Maximising the entropy of the system is the most logical way to assign probabilities to the microstates of the system, given access only to a limited subset of observables. The same 'MaxEnt' principle is quite general and applies to all statistical analysis, not only physics. The Lagrange multiplier $\beta$ is identified with inverse temperature by comparing the outcome of this abstract procedure to the experimental facts of phenomenological thermodynamics.
If you are interested in the actual dynamics of equilibration, there has been a lot of literature on this recently, especially in mesoscopic systems. Particular focus is laid on the integrability of the system: non-integrable (chaotic) systems do thermalise, whereas there is a fair bit of evidence that integrable systems do not thermalise properly. Intuitively, this is because integrable systems have a maximal set of locally conserved quantities so that, even when in contact with a heat bath, the memory of the initial conditions is never quite lost.
See, for example: Dynamics of thermalisation in small Hubbard-model systems and Thermalization and ergodicity in many-body open quantum systems, if you search 'thermalization' (sic) on arxiv then you will find many more.