[I'm assuming you mean DOS FAT filesystems (FAT12, FAT16, FAT32) - anything else might be different]
> Wasn't at some distant time in the past deleting done by just renaming a file and changing the first character to a question mark?
That is just the entry in the directory listing - it would still walk the file allocation table and mark the relevant blocks as unused. The FAT operated as a collection of linked lists - the directory listing mentions the first block and each entry in the FAT states which the next block is for a file or 0 if it is the last block. Really a sub-directory was just a special file containing filenames and other properties so deleting an empty directory follows the same process. The root directory is a special case, being of fixed length (12 blocks IIRC) in a fixed position of the structure.
> I think that also applied to folders: Delete a folder's "file", and all the contents are gone, recursively.
No, you couldn't delete a directory with contents by default. Ordering a recursive delete would perform a depth-first search-and-delete on each individual object.
> Not sure how they found free blocks when creating a file though.
As the FAT had been updated, it was a simple first-empty-block search.
Unless something had deleted something just by editing the directory entry, in which case the blocks would be left alone as they would still be marked as in use. I did see this used as a way to try hide sensitive information without it getting overwritten, both as a naive copy prevention mechanism and a "hide my porn" technique.