I understand that once endgame tablebases get checkmates, they do retrograde analysis and are able to calculate forced wins. However, how do they calculate the checkmate in the first place? Do they just use brute force?
Yes, endgame tablebases are calculated by brute force. That's why we only have complete 7-men tablebases today (which were published in 2012).
When stockfish finds a mate with more pieces than stockfish has calculated until only 7 men are on the board and the tablebases give stockfish the solution for the rest.
Roughly, yes. To build a tablebase for a certain material combination you will want to have every legal configuration of those pieces in memory. (in practice one can optimize that a bit) Then you check which of the positions are already checkmate. And yes, then you work backwards and find longer and longer wins. (and then all remaining positions that aren't wins for either side are draws)