It is widely accepted that the nucleation of graphene on transition metals is related to the formation of carbon clusters of various sizes and shapes on the surface. Assuming a low concentration of carbon atoms on a crystal surface, we derive a thermodynamic expression for the grand potential of the cluster of N carbon atoms, relative to a single carbon atom on the surface (the cluster work of formation). This is derived taking into account both the energetic and entropic contributions, including structural and rotational components, and is explicitly dependent on the temperature. Then, using ab initio density functional theory, we calculate the work of formation of carbon clusters CN on the Ir(111) surface as a function of temperature considering clusters with up to N = 16 C atoms. We consider five types of clusters (chains, rings, arches, top-hollow, and domes), and find, in agreement with previous zero temperature studies, that at elevated temperatures the structure most favoured depends on N, with chains and arches being the most likely at N10. Our calculations reveal the work of formation to have a much more complex character as a function of the cluster size than one would expect from classical nucleation theory: for typical conditions, the work of formation displays not one but two nucleation barriers, at around N = 4-5 and N = 9-11. This suggests, in agreement with existing LEEM data, that five atom carbon clusters, along with C monomers, must play a pivotal role in the nucleation and growth of graphene sheets, whereby the formation of large clusters is achieved from the coalescence of smaller clusters (Smoluchowski ripening). Although the main emphasis of our study is on thermodynamic aspects of nucleation, the pivotal role of kinetics of transitions between different cluster types during the nucleation process is also discussed for a few cases as illustrative examples.