A little bit of history:
(from the top of my head, there is very little to find about this on the web I think, even in Spanish):
At some point during the Cuban Revolution and before I was born, being in possesion of any foreing currencies in Cuba became illegal (unless you had a special permit from the government). Many Cubans spent time in jail for this reason. Diplomats, tourists (which were rare at that time) and foreigners with a permanent or temporary residence were also allowed to use foreign currencies, and there were special stores (with imported products that could not be found anywhere else in the country) that only they could use, at that time these stores were commonly called "diplo-tiendas". There was also an alternate currency called "exchange certificates" that only diplomats could use and were only valid on those stores.
After the fall of the Berlin wall, Cuba started to fall into a deep and accelerated economical crisis, the Cuban government started to allow regular Cubans to use this alternate currency in those "special stores" and encouraged them to give away their gold and jewelries in exchange for this new currency. This currency was called by Cubans as "chavito" (no idea where the word came from, I was a child at that time) and the name is still used today in a lesser degree. This was the start of the two currencies system.
In 1994, during the worst period of the economical crisis, the Cuban government decided to open the country for tourism, foreign investment, and small private business. At the same time, they legalized the possession of foreign currencies, and more of those "special stores" were built all around the country. They assumed at that time that only a small percent of Cubans would ever be able to go there, and this was all supposed to be a "short-term temporary measure". Their goal was to keep tourist and foreign companies as segregated as possible from regular Cubans, but at the same time stimulate the flow of strong currencies into the country.
They started to print yet another new currency that could be exchanged at a 1x1 rate with US dollars, and when you paid with "real dollars" for products and services, you would get your change in that alternate currency unless you explicitly requested otherwise. Later on in 2004 the government decided to forbid using foreign currencies at stores and hotels, and they forced Cubans and tourist alike to exchange their foreign currencies for the Cuban Convertible Pesos. And this is how the mess became permanent.
The two currencies:
Tourists are allowed to posses and to use CUP, but there are certain services and products that are subsidized by the Cuban government, just for Cubans (like theaters, concerts, museums, movies and the food rations that all Cubans receive on a monthly basis). Tourists will have to pay a different price in CUC for those services, and of course there are no subsidized food rations for them.
However it might still be a good idea to have some CUPs available, since buying food from street sellers and fruit/vegies stores or taking public transportation (including the "shared" taxis called "boteros") is a lot more cost-effective when paid using CUP, specially if you have a Cuban friend (and I mean a real friend) to walk around with you.
The main concern when using the two currencies are the scams, you need to know all the bills and coins of the two currencies.
So we have Cuban Pesos (CUP) and Cuban Convertibles (CUC).
At the time of writing, 1 CUC = 24 or 25 CUP (most of the time), and 1 CUC = 1 USD (most of the time). These exchange rates have been "artificially fixed" by the Cuban government for many years, however they vary depending on the situation. If you want to buy CUC using CUP, the rate will likely be 1 CUC = 25 CUP, if you want the opposite, the rate is likely to be 1 CUC = 24 CUP, and if you want to pay for services (like a taxi,with prices usually set in CUP), using CUC coins, the rate is likely to be 1 CUC = 20 CUP. For example in order to pay a taxi(botero) trip that costs 10 CUP with CUC coins, you will need 2 coins of 25 CUC cents, or 10 coins of 10 cuc cents, etc.
The main difference between the bills are the colors, as you can see in the picture below, CUP are kind of monochromatic, while CUC have many colors in them:
Pictures for all possible CUC bank notes can be found here:
Another difference is the presence of monuments of historical characters in CUCs instead of the picture of the person found in CUPs.
Note that CUP bills that are about 20 years old or more were also printed in many colors, but they are not longer used these days and it would be very unusual to come across one of these. In case you do come across one, they all look more or less like this:
The coins are also easy to tell apart, coins from CUC have all an octagon around them, and they are stamped with landscapes. Coins from CUP are all stamped either with a star or with a picture of an historical character, namely Che Guevara - 3 cup, Jose Marti - 1 cup and (currently rarely found) Camilo Cienfuegos - 0.40 cup.
Most common scam:
When receiving change in coins, if you get several 1 CUC coins, always review each of them, make sure that you are not getting a 3 CUP coin instead (the one just above with Che Guevara). They are roughly the same size and color, but 8 times less valuable.
The Cuban goverment is currently taking measures (slowly) to eliminate CUC as a currency, for this reason CUP can now be spent almost everywhere (but not the reverse), and when prices are displayed just in CUC the regular CADECA conversion rate will be applied if you want to use CUP.
As of January 2016, state-owned companies (for example most of the stores and supermarkets) are starting to accept some major credit cards as method of payment for goods and services (VISA and MasterCard for example), at least in Havana, so you could also use that as a way of avoiding dealing with currencies. Note that every time you use a credit card, the store rep will ask for a piece of ID and collect as much personal info as he/she can, I guess it will take a few years before they get used to the change and become less paranoid.
As of August 2017, It is illegal for Cubans and tourists alike to export CUC bills or coins.
Cuban citizens and residents can export/import CUP up to 2000.
BANCO CENTRAL DE CUBA (Central bank of Cuba): RESOLUCIÓN No. 18 /2012
UPDATE October 16, 2019
The Cuban government just announced that they will open a new store chain across the country that will only accept USD as currency, but never in cash, just magnetic cards (like regular credit cards for example).
These stores will not accept CUP or CUC. So Cuba now has three currencies... yey!
UPDATE February, 2020
The Cuban government is taking more steps into removal of CUC as a currency.
CUC is currently not accepted anymore inside airports once you pass immigration/customs, and there is no way to do currency exchanges anymore at that point.
If you happen to have CUC with you at the moment of your departure, make sure to change them back to a foreign currency before you pass immigration/customs.
Update December 2020
CUC will be retired starting on January 1st 2021.
It is unknown at the moment which currency tourists will use from there on.