How/what is the crime rate in Cuba? Is walking around in Havana and travel by car through the country reasonably safe for travellers?
This one is tricky... From what I have heard from latino-american friends, criminality rate in the rest of Latino-America is in general higher than in Cuba, probably because firearms are strictly and effectively forbiden by the government.
HOWEVER! I would not recommend a foreigner to drive a car in Cuba. If you run into an accident and someone gets hurt, the justice system will destroy you. In Cuba, you are guilty until you prove otherwise.
More recent case (in Spanish):
Walking in Havana during the day is in general safe. During the night you can still walk around but it might be safer to do it in groups, not very far from the tourist center (which is protected by a special police group specially trained to protect tourists) and always trying to avoid talking to "dangerous looking" fellows (if you know what I mean).
I visited Cuba in July 2011 together with a friend. We traveled from Havana to Santa Clara and down to Trinidad and back. And by personal experience can tell you this:
As Jonik wrote as well, there are very high penalties in crimes related to tourists. In fact there are laws which forbid Cuban citizens to hang out with tourists. Meaning walking around on the streets with you and talking to you. In Havana especially this law is enforced by many police checkpoints. We found this out because we were running around town with our Cuban friend, and we got stopped at least 5 times by the police. In every control they only asked our Cuban friend for his ID and papers, and payed no attention to us at all. In the first control we told the police officer that we were friends and it was okay, upon which he called the police headquarters and made our friend officially responsible for us. So he made sure that no harm was done to us ;)
Other than that, you have to be prepared that everyone tries to get money from you. Although every Cuban has a job, their wage only covers around 70% of their expenses. The other 30% must be covered in a more creative manner. Many people sell art on the streets, but many more will ask you for money in exchange for a picture with them, 'original' cigars etc. so beware and think. All the people we met in Cuba were very friendly and good fun to hang out with. The 'casa particular's are an amazing way to experience Cuba btw. look it up!
Travelling by car in Cuba as far as i know is safe. BUT you should be aware of the following. Your rental car will be a modern (!) car and clearly marked as a tourist rental car by a red numberplate. They stick out of traffic quite a lot since most cars are very old and beaten up.
Alternatives are: tourist bus system. There are tourist buses going nearly everywhere. Of course they are overpriced, but you'll have a seat and a roof over your head while driving. Then you have hitchhiking, which is enforced by the state. And the local buses which are either small trucks or their lovely metrobuses which can transport between 250 and 300 people and are dirt cheap.
The wikitravel page on Cuba is very good: http://wikitravel.org/en/Cuba#Get_around
I recommend hitchhiking in Cuba! ;) Definitely a great experience!
(I don't know about travelling by car, but I can answer the walking around bit. Also, I'll skip posting links and just tell what I've seen.)
Cuba as a country and Havana as a large city are both relatively safe. Especially if compared to many other places in Latin America (or for that matter, large cities in North America). Personally I didn't experience any threatening situations on the island during the ~3 weeks I spent there in 2008 (mostly in Havana, Cienfuegos, Trinidad, Camagüey). Situation may be different after the hurricane turmoils in recent years, but not by much I guess.
So yes, travellers can generally walk around without problems. Still, there are places, like Centrohabana, where it may not be the best idea for you as a yuma (foreigner) to wonder around by yourself late at night.
That said, what yms wrote ("During the night you can still walk around but only in groups, not very far from the tourist center") sounds overly paranoid/silly to me. I walked around a lot even late at night (for example on Malecón, the seaside avenue, and in Vedado), usually alone, and had no problems. Of course one could say I was just lucky. I'd say common sense gets you far in most places and situations.
(Oh, I didn't go to the easternmost parts myself, but I remember my guidebook had a warning about Guantánamo nightlife:
Dunno, maybe that's true.)
I've sometimes wondered why Cuba is relatiely safe. Specifically, if this is because there is less of extreme poverty (as in not having food to eat) in Cuba than in most of Latin America (which is a fact), or because of the very harsh penalties they have for crimes against tourists (who are very important nowadays to the country's economy). My best guess is that both things affect this. Also, in many places, like central Havana, there's a copious amount of police officers on the streets. In any case, during the 1990s when Cuba was going through an much rougher period economically, tourists were much more likely to be robbed, to my understanding.
One thing you will certainly encounter is people "hustling" with you. In some places you get this a lot (e.g. Havana Vieja), in other places almost not at all (e.g. Vedado in Havana; towns such as Cienfuegos). Some people doing this are more aggressive and might even follow you around, downright begging or demanding for some money. Many are actually very friendly and interesting to talk with, and it may far from clear if they're trying to benefit from you or if they're genuinely interested because you're a foreigner. (Also, male (jinetero) and female (jinetera) hustlers usually take a different approach to the business; men will get you "really good cigars cheaply" or take you to a nice restaurant or whatever you are interested in, whereas women, if you're a guy, will offer their company to you. I guess it happens the other way around too.)
Sometimes this can get annoying, but generally I wouldn't count it as a big safety risk. If you get tired of it, get out of Old Havana and go to less touristy places.
(Btw, if you're going to Varadero, it's practically guaranteed to be safe, but then it also has very little to do with real Cuba.)
All in all, fear of crime definitely shouldn't keep you from visiting Cuba. :)