The Boolean modifier needs a manifold mesh to work properly, see the [wiki][1]:

> This means that this modifier will only work properly for the
> intersection of faces of the two meshes that will result in another
> closed loop of edges (filled with faces), creating a new resulting
> face topology.

Removing the middle section of the cube should fix it:  

![enter image description here][2]

You may need to recaclulate the normals (<kbd>Ctrl</kbd><kbd>N</kbd>)

Also ensure that

* The Modifier is applied to the cylinder.

* The *Operation* is set to *Difference*:

 ![enter image description here][3]

In addition to the *Knife project* tool mentioned by Haunt_House, You may want to use the Knife tool for this:


In edit mode, press <kbd>K</kbd> to start the knife tool and <kbd>C</kbd> to enable *Angle Constrain*. (you may need to hold shift at some points to place a cut, due to the view not being aligned perfectly to the topology)

![enter image description here][4] ![enter image description here][5]


  [1]: http://wiki.blender.org/index.php/Doc:2.6/Manual/Modifiers/Generate/Booleans
  [2]: https://i.sstatic.net/vn81C.png
  [3]: https://i.sstatic.net/GHJLL.png
  [4]: https://i.sstatic.net/WdFXS.png
  [5]: https://i.sstatic.net/s41Nt.png