For example, how do two charged particles know that they are to move apart from each other? Do they communicate with each other somehow through some means?
Yes, specifically the electromagnetic field. To give a simplistic view, a charged particle produces an electric field to indicate its presence and a magnetic field to indicate its motion. Any disturbance in these fields propagates outward at the speed of light. Another charged particle some distance away can react to the fields; if it "feels" the presence of an electric field, it will move in response.
I've heard some people tell me that they bounce together messenger photons. So does one electron receive a messenger photon, go, "Oh hey, I should move in the direction opposite of where this came from, due to the data in it", and then move?
The idea of the messenger photon is really just an analogy. Personally I don't think it's a very good one, but we don't really have anything better. The thing is, even though disturbances in the EM field propagate like waves, when a particle reacts to such a disturbance, it acts as though another particle collided with it. In order to make this fit with our intuition, we're forced to invent the idea that there are particles, or quanta, associated with the electromagnetic field, and we call them photons.
Aren't photons also associated with energy, as well? Does this type of mediation imply that electrons give off energy in order to exert force on other electrons?
Yep. To make sense of this, you really have to consider the whole system of both electrons, as well as the EM field itself. Each electron "feels" the electromagnetic field produced by the other, so both electrons' motions will change in such a way that the total energy is conserved.
Every electron is repelled by every other electron in the universe, right? How does it know where to send its force mediators? Does it just know what direction to point it in? Does it simply send it in all directions in a continuum? Does that mean it's always giving off photons/energy?
This is one of those cases in which it makes more sense to think of disturbances in the EM field as waves, which can certainly be radiated in all directions. However, the electron only disturbs the field when its motion (or quantum state, rather) changes. An electron stuck in a single quantum state, such as an atomic orbital, won't be radiating any energy.
The bottom line is that I would advise you not to take the idea of "messenger photons" too literally. It's just a model that works in some situations but not in others.