Unity version 4.3 now contains a new primitive type "Quad" which is the "2 triangle plane" described below.
You will want a 2 triangle plane ideally, generate the Mesh first then instantiate a new GameObject and supply the MeshFilter component with that programmatically generated mesh:
This is a useful community script as well for camera facing billboards
Once you have generated the billboard as runtime drag it from the Hierarchy into the Assets panel to create a prefab for use in the future.
Alternatively use Blender or another external modelling software to create a 2 triangle billboard and use that... that would be the most efficient method.