Why does a car engine not do work if the wheels don't slip? I saw this mind boggling result that if the tires don't slip then the work done by an engine to move a car is zero. Why is this true? Moreover, what does this truly mean?
Update: Sorry about not being clear, but I was talking about an idealised case where air resistance is negligible and the tires are perfectly rigid and there is no internal friction at play.
 A: Unless you are talking about in the very limited sense where at the molecular level some number of molecules of the tire must rub off in order to transfer a force to the car, the statement: "if the tires don't slip then the work done by an engine to move a car is zero" is wrong.
Tires slipping in the normal English language sense has nothing to do with energy transfer or work. Where did you read that? You could have a car with gears for wheels running on a geared road that would not slip at all, there would still be work involved in accelerating the car.
Work is defined as the amount of energy transferred by a force acting through a distance. It can also be measured by torque acting through a rotation. The work done by an engine is measured in this way by torque and rotation. 
You said: "the work done by the engine to move a car." If a car accelerates slow enough that the tires do not slip, there is still torque being applied to the engine and wheels to cause the acceleration. Even in the case of a car that is moving at a constant speed, in order to overcome the drag of the car moving through the air and the frictional drag of the drivetrain, the engine must apply torque to the transmission. The amount of energy the engine supplies exactly matches the energy drag of the air and drivetrain for a car that is moving at a constant velocity.
A: The car engine is doing work on the car in the colloquial sense, in that the energy produced by the engine ends up moving the car. Further, the engine is doing work on the car in the technical sense, in that if you trace the energy flows through the car, you will find they all trace back to the engine. But the energy flow in detail is complicated, because energy flows are not intuitive. The only way to understand them is to consider simpler examples first.
Kinetic energy depends on the reference frame. If you add energy to an object by speeding it up, there is always a reference frame where the object is slowing down. In this frame, you are taking energy away from the object and transferring it to you. For example, if you push on a block to speed it up to 10 m/s to the right, in a frame moving 10m/s to the right, you are slowing down the block to 0 velocity (doing negative work), and your feet are doing more work than this on the moving ground, so that you are doing the same net amount of work on the ground.
If I am riding on a subway and I lean on a pole against the direction of motion, the pole is not doing any work on me in the subway frame. But in the rest frame of the tracks, the pole is pushing me in the direction of motion, so I am absorbing energy from the pole, which is then transmitted through my feet right back to the train, and through the train right back to the pole. So there is a closed circuit of energy, like a closed circuit of electricity, and the amount of energy flowing through this circuit depends on the frame.
The reason this happens is because a static problem of forces supporting objects has a momentum flow, and the momentum flow is the same in any frame (in Newtonian mechanics). The momentum mixes up with the energy when you do a boost, in a nontrivial way.
To understand what the invariant thing is, you should know the following theorem:


*

*The net change in the kinetic energy of a point particle is the net force on the particle dot the velocity.

*The net change in nonrelativistic kinetic energy of an isolated system (a system obeying the momentum and center of mass conservation laws) is independent of the reference frame (the energy is located in different places in different frames, though).

*The difference between the kinetic energy gained by a subsystem and the work done on it is the energy converted from other forms, or dissipated as heat.


In the case of the car, in the rest frame of the road, the engine is generating energy, which is going to the wheels. The part of the wheel in contact with the road is not slipping, so the road does no work on this part of the wheel, but the bottom of the wheel does do net work on the rest of the wheel (when the car is accelerating or maintaining speed in the presence of drag). If you treat the wheel as a unit, you can say that the road is doing work on the wheel, since it is applying a force to the wheel in the direction of net motion of the center of mass. This is what the authors of the book mean.
This idea is extremely misleading. The wheel is not doing work on the ground (in the rest frame of the ground), since the ground is not moving. This is not a paradox when you treat the car as a unit, because the wheel is absorbing energy which comes from the work done on it by the axle. This means just means that the car-unit generated the energy which is added to it from the direction of the ground, but which is actually generated in the engine. The energy flows to the end of the wheel, distributing itself evenly due to the equilibrium stresses that get generated in the car. You can think of it as the energy going to the wheels, and getting reflected at the no-slip boundary conditions, which forbid the energy from leaving the car. It is not clear that the word "reflection" is optimal i this case, the stresses that are set up through the wheel and the axle reroute the energy flow to redistribute it evenly throughout the car's mass as kinetic energy.
In the rest frame of the road, the force from the engine is stressing the contact point, and these stresses do work uniformly throughout the car. Changing frame to the car's final velocity frame, the work done is the same, but now the car is pushing the ground backwards, and is doing the same amount of work on the ground.
The counter-intuitiveness of energy flow is mitigated somewhat in relativity, where the mixing of momentum and energy becomes geometrical.
A: The answer to your question depends on precisely how it is interpreted.  In my opinion, the clearest way of understanding a car driving on the road does in fact have the engine doing work on the car, but it is possible to define the system involved such that this is is not so.  However, under this interpretation, the engine does no work on the car regardless of whether or not the tires are slipping.
To explain this distinction, I'll first give an example of work, then talk a little about work on the driving car, then finally discuss no-slip tires.  I think this is a fairly-tricky issue, so please excuse the length of my response.
At Anna's request, let's assume no air drag, no internal friction, and no slipping.  If the car is moving at a constant velocity, then the engine can be turned off, allowing the car to coast.  There is clearly no work done and no change in energy in this scenario, so we'll talk about what happens as the car accelerates.
Work
In physics, "work" is a way of transferring energy into or out of a system.  We say that a force does work on a system, thus adding energy to it.  Work is defined by the equation
$$\textrm{d}W = \vec{F}\cdot \textrm{d}\vec{x}$$
The left hand side, $\textrm{d}W$, means "a small amount of work done".  On the right hand side, $\vec{F}$ is the force that is doing the work, and $\textrm{d}\vec{x}$ is the movement of the part of the system where the force is applied.  This does not particularly look like a change in energy, but it is possible to show, using Newton's laws, that work, as defined above, turns out to be the same as the change in kinetic energy induced by the force.  (see work-energy theorem)  
We need to keep in mind for later that although work done on a system induces a change in its kinetic energy, not all changes in kinetic energy are due to work being performed.  For example, if I have a gerbil in a cage, and the gerbil starts running, the cage didn't go anywhere, so $\textrm{d}\vec{x} = 0$ for the system (gerbil + cage), so the work done on the cage/gerbil system is zero.  Nonetheless, it gained kinetic energy.  This is an internal conversion of energy from chemical energy in the gerbil to kinetic energy.
For an example of work, suppose you put your car in neutral and I stand behind it and push.  If I push with a force of $100$ newtons, I do $1$ joule of work for each centimeter the car moves.  In this example, $\textrm{d}W = 1 \textrm{J}$, $\vec{F} = 100 \textrm{N}$, and $\textrm{d}\vec{x} = 1 \textrm{cm}$.  The "$\cdot$" symbol means the vector dot product.  As long as the force and the motion are in the same direction, this is the same as normal multiplication (but if the force is at an angle to the motion, the work goes down; we won't worry about this in the rest of the answer).  This work is the change in the kinetic energy of the car; the car speeds up some while I push.
It's important to define the system you're doing work on.  In the example above, I considered the system to be your car.  Then I applied an external force with my body.  In an alternative view, we could define a system that consists of the car and me together.  Then I didn't do any work on the system at all since, by definition, only external forces can do work.  Finally, we might consider the system to be just the back half of the car.  In this case, I'm still the external force and I did the same amount of work, but all that work went into the back half of the car.  The back half of the car then in turn did some work on the front half of the car.  This tells us that when I push on the back of the car, the car compresses a little, creating a force between the front half and back half that's half the size of the force I'm pushing with (since half the work done on the back half goes into the front half, giving those two halves the same change in speed).  This is really true.  If you slice your car in half, then hold the two halves together with some slices of white bread, when I start pushing on the back of the car the white bread will get crushed.  Thus, the internal stresses in a car are different for front-wheel-drive and rear-wheel-drive vehicles.
Net Work on the Car
Let's take our system to be the entire car as it drives.
The car might be going at $45 \textrm{mph}$ or $20$ meters/second.  In that case, in one second the car travels $20 \textrm{m}$.  If, in one second, the car goes from $20 \textrm{m}/\textrm{s}$ to $21 \textrm{m}/\textrm{s}$, and the car has a mass of $1000 kg$, then the change in the car's kinetic energy works out to $20,500 \textrm{J}$.  Assuming this is work done by an external force (me pushing, for example, although it's unlikely!) the work done on the car is $20,500 \textrm{J}$.
No-Slip Tires
The above analysis is wrong - the assumption that work is done by an external force is incorrect.  The car is accelerating, so there must be an external force on it.  But it turns out that external force does no work.
The external force on the car is the force from the road on the tires.  Because the tires are not moving with respect to the road, this force does not do work.  Thus, the road does no work on the car.  This is as it should be.  Everyone knows the road is not making your car go.  The road cannot do work on your car because the road has no energy to give up.
Similarly, there is a force equal and opposite from your tires to the road, but again this force does no work.  This says that your car does not put any energy into the road.  This allows a car engine to be more efficient than a jet engine.  A jet engine works by pushing air backwards.  This air is moving with respect to the jet, and so the jet does considerable work on the air.  That means that lots of the energy used by the jet engine goes into the air, and is wasted from the viewpoint of making the jet go.
When I'm pushing the car, my feet don't move while in contact with the road, so again no work is done on us.  In both the case of me pushing (as long as I'm part of the system) and the car driving, the car's increase in kinetic energy is not due to external work, but to a conversion of chemical energy to kinetic energy completely within the system.
The Engine
Since the engine is inside the car, if the system we consider is the car itself, the engine does no work on the car.  A system can't do work on itself, by definition.  Instead, the engine spins an axle that spins the tires, adding kinetic energy to the car, but not doing work.  This is why it's possible to say the engine does no work, and it is not dependent on whether or not the tires are slipping.
Since the kinetic energy of the car is changing, we might learn something more by redefining the system.  If we define two systems, one being the body of the car minus the engine, and the other being the engine, now work is indeed being done.
The engine does work on the car.  It does this by spinning an axle.  To spin the axle, the engine must exert force on the outside edge of the axle, and since the outside edge of the axle is moving, the engine does work.  (As inflector pointed out in his answer, this work is more easily calculated in terms of the torque on the axle as it rotates, but the two descriptions are equivalent).  All the energy the car gains comes through the engine, so in this scenario the engine does all the work to accelerate the car.
The car also does work on the engine in this case.  The car exerts a force on the engine.  This is a structural force that keeps the engine in place inside the car.  The car is paying back a portion of the energy it gained when the engine did work on it.
Conclusion
Two different people (in the same reference frame) can observe the same events, but disagree on whether work is done during them, or on how much work is done.  This is because work is a transfer of energy between systems, so that if the two people define their systems differently, they will calculate different values for work done (and for heat exchange).  
In light of this ambiguity, it is correct, although incomplete, to state that the engine does no work.  This is not dependent on the no-slip tires, and is an artifact of defining systems such that the engine and car are part of the same system.
No slip tires imply that the road does no work on the car, and that the car does no work on the road.
A: It's fairly simple:
The work done $W$ must correspond to a change in the kinetic energy of the car $T=\frac{1}{2}mv^2$. It any work is done, there must therefore be a corresponding acceleration.
If the car is moving at constant velocity, then there is no work done. The engine counterbalances the air drag.
If the wheels slip, then the car slows down due to drag. Work is done by air to slow down the car. The engine still performs no work on the car as it cannot possibly alter the speed if wheels slip.
A: In the idealized scenario, you turn off the engine and the car keeps going forever, since the engine is not doing any work.  If the car is completely at rest, then the engine is doing work.  Maybe not in regards to the tires against the road, but somewhere in the system, pistons are moving, and a crank-shaft is turning the wheels.  That initial impulse that gets the car moving happens over some distance, and that is where your work is.  But remember, work only happens when velocity changes (in the ideal scenario).
A: When you are accelerating, (in a RWD car) the rear tires are turning faster than the speed of the car itself. The "slip" is held to the road by traction.
