How to do a subtractive boolean
- Make sure you've selected the object to be carved from, and add a Boolean Modifier (when in Edit mode, look for a wrench icon on the right-side panel when you have the object to be carved from selected - this is the modifier panel).
- For the modifier's Operation choose "Difference".
- For the Object field choose the object that will do the carving.
- Apply the Boolean Modifier and delete your carving object.
Tip: For step 4, as an alternative non-destructive approach you could also leave the modifier on without applying it, and hide the carving object from rendering. If you want to see the carving object's shape and its effect at the same time, instead of totally hiding it in the viewport you could go to the Object Tab and set the Maximum Draw Type to "Wire".
Tip: Low-poly meshes may not boolean so well, while high-poly meshes can be slow to calculate or in extreme cases even crash Blender. So consider your mesh density before using a boolean.
Tip: If either mesh's normals are facing the wrong direction you will have problems when doing a boolean. Recalculating normals can sometimes be a solution if you find a boolean is not working as expected.
Tip: Remove doubles. If your normals are just fine, the next thing to try is removing doubled-up vertices. This can be done from within Edit Mode by pressing W and choosing "Remove Doubles". At the top of the interface near the tiny Blender logo a message will momentarily appear saying "Removed __ vertices". If this number is not 0 then you'll know that some doubles were removed and that the problem has probably been fixed.
Tip: Large n-gons can cause booleans to fail. The solution is to convert to triangles. Here is a post addressing this problem in more detail.
Tip: Avoid booleans if you plan to SubSurf. Modeling with booleans may be fine for simple hard-surface geometry, but if you then put a Subdivision Surface Modifier on that object you can expect unsightly results. This is because for things like subdivision and mesh deformation topology is important. An all-quad mesh is ideal, but still requires some good old-fashioned manual modeling to create. It's worth learning the concepts of edge-flow and poles if you intend to create a low or med-poly mesh with "holes" cut into it that still looks good when SubSurfed.
Tip: Sometimes using "Smooth" shading doesn't go so smoothly after modeling with a boolean. This has a lot to do with the topology issues I mentioned above, but there is a quick fix that is suitable for many cases. Navigate to the Mesh context tab and check the Auto Smooth option. Adjust the slider until the shading looks desirable in the viewport. Here is a before/after example:
Note that regardless of the angle specified for Auto Smooth, any edges that have been Marked Sharp (CtrlE) will be sharp as long as the Auto Smooth feature is enabled.
The solution for your case
It was caused by conflicting normals, as I mentioned in one of the tips above. In fact, you can even see from the darkly shaded geometry in your screen shots that some of the normals are inverted. After recalculating normals on both objects I was able to boolean just fine. Here's the solved file:
