Is most of the weight you lose actually released as carbon dioxide when you exhale?
Let's start with:


  How much is heat energy?


2000 kilocalories per day, considering $E=mc^2$, is 
$9.3 \times 10^{-8}$ grams


  is all the carbon released later when you exhale? 


No.  Brainstorming, the others ways would include: feces, urine, perspiration, flatulence, shedding skin, hair and nails, mucous from nose and mouth, for women: menstruation, vaginal discharge, lactation, and giving birth, and for men ejaculation.  

According to The Value of Human Feces:

Per day the amount of carbon excreted in feces is 21 grams and in urine is 7 grams.

According to The Composition of Human Perspiration Proc R Soc Med. 1934 May; 27(7): 839–848, a typical amount of perspiration a day is 700mL, and per 100mL the main carbon containing compounds are 20 mg urea, 20 mg glucose and 5mg amino acids.  So clearly less than 1 gram of carbon loss per day from perspiration. If we were considering loss of salts instead of just carbon, that would be about 3 grams per day from perspiration.

For menstruation, blood loss is about 40mL per cycle, and blood is 92% water, so maybe 1 gram of carbon on a heavy day of a period.  

Skin loss per day is 1.5 grams according to Cells for life, cells for an instant.

A highly controlled study having a person in a chamber for 24 hours and analyzing the air found 653g of CO2 or 178g carbon "A Respiration Calorimeter with Appliances for the Direct Determination of Oxygen" Carnigie Institution of Washington Publication 42.

So, for a person that is not lactating or giving birth, I would estimate about 30 grams per day of carbon loss is other than from exhaling carbon dioxide.  Therefore:

About 86% of carbon loss is through exhaling carbon dioxide.  

However, this will certainly vary depending upon the amount of indigestible carbon such as fiber, in ones diet.

Also, if mass loss through nitrogen and phosphorous (but not hydrogen and oxygen) were also considered the loss through breathing would come down to about 80%.  Inclusion of salts would bring this percentage down further.

The sum of water from feces, urine and respiration is about 1.8 kg per day and the total mass emission of the body is 2.6kg, according to the Carnigie source above.