Yes, they do. For a look at survival of Lactobacillus and other bacterial species after multiple freeze/thaw cycles, check out Harrison 1955 (below).
The awesome hand-drawn graphs show that many bacteria survive after being frozen for 11 weeks. There's also a figure on the following page showing that many bacteria also survive after multiple freeze-thaw cycles, but I won't include that page here for brevity.
Prof. Don Schaffner of Rutgers also supports this conclusion:
So it's possible, even likely, that frozen and thawed yogurt will contain
living lactic acid bacteria, although it may only be 10% or 1% of the
total number of bacteria that were there before the yogurt was frozen.
I couldn't find a great deal of official resources on the topic, hence the paper from 1955 and random quote from a food science professor. However, in a lab setting, scientists regularly freeze bacteria and even eukaryotic human cell lines. Usually scientists use a cryoprotectant like glycerol, but many foods (like yogurt and ice cream) may contain an FDA-approved cryoprotectant (Wikipedia):
One recent, successful business endeavor has been the introduction of [anti-freeze proteins] AFPs into ice cream and yogurt products. This ingredient, labelled ice-structuring protein, has been approved by the Food and Drug Administration.
So, yes, at least some of the bacteria in your frozen yogurt are still alive, and will have whatever beneficial/harmful/lack of effect when you ingest them.
Judging from figures 1-3 above, bacterial survival depends on how long and how many times you freeze the bacteria. My rough estimates of the graph above say 40%-10% after a single freeze, and after multiple freeze-thaws getting into the 1% range. Also, it doesn't matter whether you thaw it first or eat it frozen as far as bacterial content is concerned, the bacteria will be unfrozen either way when they reach your digestive tract.