What kind of electrical outlet is this, and how do I replace it?
The holes in the back accept straight wire and are electrically connected directly to the screws on the side.  The holes are a newer connection method while the screws are more traditional.  Tightening the screws presses contacts against the wires in the holes and holds them in place.

In this case, you have a feed wire going to one and then continuing on to another place from the second.  By the electrical code (at least in Ontario), you're not allowed to do this.  You must connect the feed to the branch and to a short "stub" wire with a marette and then connect that stub wire to your outlet (either at the screw or through the hole in the back).  Some people take short-cuts, however, and connect it this way to avoid the marettes.

Aside from that, I'll note that you have a "split circuit" outlet here.  The top and bottom outlets are on different circuits, perhaps because it's a kitchen outlet and thus they must be split circuit (by the electrical code of Ontario, anyway -- your mileage may vary) or because one outlet (with the red wire) is "switched" by some wall switch.  Make sure you break off the connector tabs between the two sockets on the new outlet so you don't accidentally short the two circuits together.

EDIT: As pointed out by @MichaelKaras, some outlets don't bind the straight-in wires with the screws but have spring-loaded clips that hold the wire and are released by inserting a small screwdriver into the square opening just above the hole.

EDIT: @MPelletier makes a great comment: US multi-wire circuits like that require either a double breaker or that the two breakers be yoked together so that you can't only turn off one. You might consider fixing the breaker box wiring for safety purposes.  That's true in Canada as well.