Render shadows over a transparent background in cycles
UPDATE:

As of Version 2.79, there is an option to make an object become a shadow catcher in Cycles.





From the release notes 


  This option will make object to only receive shadows in a way that it could be alpha-overed onto another image.


The workflow is following:

Enable Film: Transparent.



Then (Quote from the develpoer's notes)


  Create an object which matches real-life object on which shadow is to be catched.
  
  Create approximate similar material on that object. 
  
  This is needed to make indirect light properly affecting CG objects in the scene.
  
  Mark object as Shadow Catcher in the Object properties.
  Ideally, after doing that it will be possible to render the image and
  simply alpha-over it on top of real footage.


Once the plane has been marked as a shadow catcher, just render!

Again from the release notes 


  It is to be noted that shadow catcher objects will interact with other CG objects via indirect light interaction. For example, shadow catcher will be reflected in the glossy surfaces.






OLDER ANSWER:

You can do a shadow catcher using a shadow pass and different render layers to create an alpha channel for the scene:




Move the plane object (shadow catcher) to layer2.
Make a copy of the other objects and move them to layer 2.

The idea is that on layer 1 you only have your objects but not the plan, and on layer 2 a copy of your objects and the plane that will act as shadow catcher.

 
On all of the objects in layer 2, except for the shadow catcher plane, disable Ray visibility for camera. You want the plane to be visible, but the other objects should be transparent to camera and projecting shadows on the plane:


Make sure your lamps and camera are active in layers 1 and 2.


Set up two render layers:

One for the objects in layer 1 that excludes information from layer 2.

A second render layer for the shadows that includes a shadow pass and excludes layer 1.


Enable Transparent on the Film section.


In the compositor you can use the shadow pass to alter the values of the alpha channel of the object's layer. 

Add an invert node to shadow pass and plug the result as factor on a mix node (in add mode). Plug the alpha channel of the object's layer to the top socket and leave the lower socket empty.




You can control the transparency of the shadows by changing the color on the empty socket of the mix node. If you make that color white the shadows will be fully opaque, if you make it black you'll have no shadows.

Alternatively you can use the values from the shadows layer and the transparency of the shadows will be set using the values from the original scene:



For softer shadows you can add some blur: