There are two way of using a GtkComboBox widget. If you create it with gtk_combo_box_new_text(), it will hide the model from you, providing only strings. To customize this model, you can connect a cell data function to the model so that you can customize each cell before it is rendered.
The other way is to use gtk_combo_box_new(), in which you will have to provide your own GtkTreeModel, which is usually of the type GtkListStore. If you do this, you can just create it like any other tree model, using tree model columns to change the look of each row.
For more information about tree models and cell data functions, you should view this GtkTreeView tutorial:
http://scentric.net/tutorial/. It doesn't directly relate to GtkComboBox, but can be used to figure out how to create tree models.