It turns out they’re fishing. Malmok reef is on the leeward side of Aruba. That means that the wind is always blowing away from shore. If you tie a long handline to a balloon and then release it on the water, it’ll float out over the reef to the deep water where the big fish live.
They generally bait the hook with squid from the grocery store. Once when we were walking along the reef in the morning, we found some leftover squid from the night before. Some frigate birds had also found them and were swooping in to grab them.
The rig to connect your line to the balloon looks something like the one described here. After the hook gets to the deep water, you disconnect it from the balloon and pull it in. The balloon continues towards the horizon. Here’s a link that describes it all better than I can.
It’s really kind of festive to see all of the balloons bobbing on the water in the sunset every evening.