I am aware of travel agencies catering to US citizens visiting Cuba, but are those services really worthwhile? If so, how does one go about vetting them?
I don't know about the services these agencies provide, but visiting from Mexico is fairly straightforward. All you need is a plane ticket. WikiTravel Americans in Cuba article provides more details and some of the risks involved.
You don't need much to visit Cuba, most Americans get in via Mexico or another country in Central America and then just get the next plane.
Border control in Cuba will not stamp your passport, so there is no evidence that you have ever been there. Instead you have to fill out a Tourist Card, which allows you to stay in the country for 90 Days. Keep in mind that they ask for you hotel address on this card, so should have at least a booking for one night... or know a valid hotel address before you arrive.
gocuba.ca has more general tips for north-Americans visiting Cuba.
My friend just went to Canada earlier this year and then flew to Cuba. No hassle, no tourist agency required.
Depends what sort of traveller you are, but I definitely wouldn't bother with an agency when there are such easy flights from other countries.
(Fun fact: the flight he was on was the first I've ever heard of that allowed smoking on board!)
However, he was a Kiwi. For US Citizens, I recommend Chris Guillebeau's How to Travel to Rogue States and other Interesting Places article:
Cuba – The U.S. embargo prohibits American citizens from going to Havana without a good reason. Naturally, this only applies to Americans, so everyone else can freely travel to Cuba. For its part, Cuba is happy to welcome American travelers, and in fact they’ll go along with the ruse by not stamping your passport if you ask upon arrival.
You can get to Cuba by:
a) Flying to Jamaica (or elsewhere in the Caribbean) and then taking Air Jamaica
b) Flying through Mexico (Aeromexico), Canada (Air Canada and several charter companies), or the U.K. (Virgin Atlantic and others)
c) Going through the process to get “permission” from the U.S. government to visit Cuba. This can be done through a university exchange, a journalist visa, or a few other approved exceptions.
As for me, I’m waiting it out because there are a lot of other places I need to go first, and since I come and go so often, I don’t want to get put on some kind of TSA terrorist list because my passport was scanned in Havana. Of course, if you’re not a U.S. citizen, then it’s not difficult at all to get to Cuba.