How general is the relation between entropy and energy? I am not a physicist, and my understanding of entropy is based on information theory and probability theory, rather than on physics. 
I am somewhat confused by how physicists think of entropy, and the role that it plays. For example, entropy has units $\frac {\text{energy}} {\text{temperature}}$, rather than being a dimensionless quantity, which is how I think of it. (After all, entropy is a concept that applies to a very general set of systems. All we need is some kind of probability distribution).
In particular, I have read that 

Temperature is the increase of a system's energy when an entropy bit is added

This suggests that there is some kind of hard universal relation between energy, temperature, and entropy. Is this statement really a universally applicable, hard law? Does "energy" always increase exactly by temperature $T$ when we "add a bit" (whatever that means practically)?
More generally, I am confused by the fact that there is any hard relation at all between energy and temperature. I would have guessed that the relation depends on the system, and the form of the energy (kinetic vs potential, etc).
(sidenote: It would be useful to me if there was a textbook that explains physical entropy in the language of probability theory information theory, and states the results without relying to much on physics knowledge.)
 A: Yes. The relation is
$$\frac1T=\left(\frac{\partial S}{\partial U}\right)_{V,N}$$
where $T$ is the temperature, $S$ is the entropy, and $U$ is the internal energy. The partial derivative assumes that the volume $V$ and the number of particles $N$ are held fixed.
This is a pretty general relationship. Even more general is the thermodynamic identity
$$\text dU=T\text dS-P\text dV+\mu\text dN$$
for pressure $P$ and chemical potential $\mu$ from which the above relation can be obtained.
A way you can reason to the first relation is the following. We know that when two systems are at thermal equilibrium that they are at the same temperature. We also know that heat (energy) flows from a higher temperature system to a lower temperature system. We also also know that at equilibrium the entropy of the entire system must be at a maximum. 
More specifically if we have two systems $A$ and $B$ that can exchange energy between each other but not with anything else, we know that at equilibrium
$$\frac{\partial S_{\text {total}}}{\partial U_A}=0$$
Since the total entropy is $S_{\text {total}}=S_A+S_B$, we have
$$\frac{\partial S_A}{\partial U_A}+\frac{\partial S_B}{\partial U_A}=0$$
But the total energy $U_{\text {total}}=U_A+U_B$ must be constant, so $\text dU_A=-\text dU_B$. Therefore we have
$$\frac{\partial S_A}{\partial U_A}=\frac{\partial S_B}{\partial U_B}$$
So we have this thing $\partial S/\partial U$ that has units of 1/temperature and are equal for two systems at equilibrium. This value must be $1/T$. This last step might seem a little hand-wavy, but it turns out to work for many systems. The ideal gas law is one such example. It also has the property we want that energy moves from higher to lower temperature systems, and this energy flow increases the total entropy of the system.
Notice how we didn't assume any specifics about our system. All we assumed is that they could transfer energy between each other. Therefore, this relationship is very general.

You also seem to have some questions regarding temperature and energy. This is why we define a heat capacity. For example, for systems held at a constant volume define the heat capacity to be
$$C_V=\left(\frac{\partial U}{\partial T}\right)_{V,N}$$
This does depend on your system. The heat capacity tells us how much the temperature of a system changes given a change in its energy. Using the above discussion then we have
$$\text dS=C_V\frac{\text dT}{T}$$
And this can be used to find the change in entropy for a process. i.e.
$$\Delta S=\int\frac{C_V}{T}\,\text dT$$
A: Making thermodynamic entropy dimensionless is trivial: it is enough to divide it by a constant with the proper physical dimensions. The Boltzmann's constant is there. $S/k_B$ is  dimensionless.
Things start to become more complex when we ask questions like the yours about the connection between information theory entropy and thermodynamic entropy. The short answer is that they do not coincide in general. Only under special conditions one can establish a link between the two concepts which, unfortunately, have been named the same way ( it is quite well known the story about why Shannon named his newly discovered concept that way).
The link between information entropy, which can be defined whenever a probability is introduced for a set of states, and thermodynamic entropy goes through Statistical Mechanics and the special way Statistical Mechanics is able to provide thermodynamics when the limit for infinitely large systems is taken.
Keeping Physics at the minimum (but it is not possible to explain physical results  completely without Physics), Statistical Mechanics can be seen as a black-box which receives the energy of the system as function of positions and momenta and provides as output a probability density function of the same variables. Probability densities may vary depending on the kind of interaction between the system of interest and the external world. Once one has probabilities, average values of observables can be evaluated and at the same time Shannon's formula can be used. Notice that at this stage one has not recovered thermodynamics yet, because finite size effects destroy some of the most fundamental properties of thermodynamic quantities, like extensiveness and convexity. In order to fully recover Thermodynamics, a final stage is required: the so called Thermodynamic Limit, which corresponds to use rations of extensive quantities, when the size of the system diverges.
Therefore, it should be clear that Shannon's entropy  strictly contains thermodynamic entropy as a special case, but not all the systems which may be described by Shannon's entropy should have a thermodynamics of any kind. An important pre-requisite is the ability of the system to have an underlying dynamics which may make the system exploring all the available states. Equally important, the existence of a meaningful energy underlying the whole mechanic evolution. The typical example of a deck of cards is a good example to show why any Shannon-like  entropy connected to the such a system (see for instance here ) has nothing to do with Thermodynamics: there is no meaningful energy which could be associated with the distribution of the cards.
