After my frustrating time at Jose Marti International Airport, I thought I'd post a quick and dirty guide for any other FTers who might find themselves in the same situation. This guide is applicable to Terminal 3, where most of us would fly out of.
Visual Guide, open in a new window. This is drawn from memory, so may be a little off.
Upon arriving at Terminal 3's upper level, wrap your checked luggage. This is available for 5 convertible pesos (cheap compared to other airports), and is quick and painless. The wrap service is prominantly displayed on the right side of the terminal, close to the entrance. There's a free service for Cubana on the left hand side of the terminal.
The center and sides of the terminal are lined with tourist tchotchkes and two areas (marked Bar) which sell food and drink. If you're hungry, I suggest buying a ham and cheese sandwich from one of the food stalls - you won't find better on the other side of security, even if you have access to the VIP lounge.
Now it's time to check in. Not as easy as it sounds.
The terminal is divided into two sections, A (left as you enter) and B (right). According to the airport signs, A is for locals, B is for tourists. Over each check-in section is an electronic sign with the flights and their status.
Don't believe them.
My flight was supposed to check in at section B, but that day they'd decided to change the sections so Air Canada was reassigned to the Cubana checkin counters. The electronic signs were never updated. And don't expect airport staff to know either, they'll vaguely wave in a random direction. The Air Canada sign I saw proudly displayed in a section with all the other airline signs (AF, LAN, etc) was never brought out.
Your best bet is to wait for the electronic sign to update to "Check-in" for your flight (approximately 2h before), then walk through both the A and B sections and look for the line of people, and the Air Canada signs over the agents' heads. Mine ended up being on the very far left of A section, not B as everyone kept insisting. There was an executive check-in line for my flight, which I took advantage of.
Upon check-in, you'll be handed a boarding pass and (if you're in executive class) what looks like a second boarding pass, but is actually a pass to the VIP lounge; I'm not sure if this also applies to airline status holders or just those travelling in executive class.
From there, you'll need to pay the airport tax, 25 convertible pesos. You'll see a sign proclaiming "Airport Tax" near the security entrance, I can't quite recall if it was just to the left or right of the gates. Either way, hand your boarding pass and 25 convertible pesos to the agent, they'll apply a holographic sticker to your pass, and you're free to go on your way.
There's an agent guarding the way to the security booths, show your pass and you'll be waved through. At the booths, line up and wait to be called over. It's the standard customs stuff, I wasn't even asked any questions, just handed over my passport, visa, and boarding pass, and was waved on. I assume older gentlemen may be questioned about cigar purchases, but I didn't rate a blink (and the 20 7" long Cohiba Esplendidos nestled lovingly in my carry on were never brought out).
After that it was the standard security deal, items in the bin, through WTMD, and on your way. No need to take off your shoes or put liquids in a separate bin, at least, I wasn't asked.
After the WTMD, proceed down the stairs and the VIP lounge is immediately on your left. Hand your pass to the lady at the desk, grab a Cristal from the fridge, and relax til your flight's ready to leave!