How would you cut a shape out of an object using another object?
Knife Project Tool

The tool you are looking for is the Knife Project tool. Here's how to use it:


Create your cube that you want to put the circle on  
Add a circle curve: SHIFTA -> Curve -> Circle  
Position the circle in front of the face you want to put the circle on, as shown here (highlighted in green):   

  
Now go to the viewport where the circle visually appears where you want your circle to be on your cube, like this:   

   
Now select the circle, then hold down SHIFT and select the cube.  
Switch into Edit mode  
Tools panel (T) -> Mesh Tools section -> Add section -> click Knife Project 
(Note: In 2.70, the Mesh Tools section is located in the Tools tab)  

This will result in the cube now having a circular hole in the front face:

  
If you now want to fill the hole with a face, select all the vertices of the hole and press F.  


NOTE: In this example, the circle is considered the Knife, which is kind of like a cookie cutter, or perhaps even a bullet, and so when you click on the Knife Project button, what Blender does is it projects/shoots the knife (here the circle) from the visual angle in your active viewport. So, make sure you have the knife visually lined up so that when it projects/shoots onto your destination object, it will make the circle right where you want it. Here are two examples of projecting from different angles:  

  

An interesting note is that in the example above where the knife is visually at an angle, the resulting face on the destination object is NOT automatically deleted (see the highlighted face on the lower example.)

Also, you can indeed use any shape as a knife: