I understand that Gibraltar was the only overseas territory that got a vote in Brexit.
Why didn’t any of the others? Were places like Bermuda and the Falklands never in the EU to begin with?
EU law applies in full to Gibraltar, but the Falklands and Bermuda (and a couple of others) are only “associated”, which means certain freedoms such as the free movement of workers and the prohibition of customs on trade with these territories apply, but not elections to the European Parliament. If you want to read more about it, Wikipedia has a page on the matter. The British Parliament took that into account when it tailored the provisions on eligibility to vote in the statute which provided for the referendum (PDF file); it made specific provisions for Gibraltar.
Cayman did not get a vote on Brexit.
For a few purposes Cayman is something of a quasi member of certain international bodies courtesy of our mother country. For example appeals on human rights matters may end up at the European Court of Human Rights, an entity of the Council of Europe.
As an overseas territory we are ultimately at the whim of the UK to determine our relationship to international bodies. This despite the fact that Caymanian citizens were granted UK citizenship by the British Overseas Territories Act and as such are considered citizens of the UK and thus the EU (at least for the time being).
Not surprisingly there is an entire Wikipedia page on Special member state territories and the European Union which goes into some detail on the issue of Gibraltar’s membership in the EU.
In short, Gibraltar was made a part of the EU by virtue of joining the European Economic Community in 1973 under the membership of the UK, an agreement predating the British Overseas Territories Act of 2002.