Rendering smoke in Cycles?
As of version 2.73 from 2015:


Make sure render engine is set to cycles (BI wouldn't create the required cycles materials)
Select the object you want to emit smoke
From the menu Object/Quick Effects pick Quick Smoke


After that a material has been created that looks like:



In order to also emit flames it can easily be extended to:



Note that the attribute names have to be exactly as they  are show 'color','density' and 'flame'.

Important settings for the Domain object (besides higher-resolution):



Important settings for the Flow Object:

Add a procedural texture and animate some properties to animate the flames.



Full tutorial: http://www.blenderguru.com/tutorials/make-fire-cycles/