How do gelatin and aluminium sulfate strengthen paper?
The process of adding gelatin and such to paper (cellulose) is called sizing. The idea behind using gelatin is that it has both a hydrophilic end and a hydrophobic end to the molecule. The aluminum sulfate (alum) is added as a hydrogen bonding linker between the cellulose and the hydrophilic end of gelatin (or some other similar molecule). Mostly this is just to prevent the paper from getting wet in the first place.

Your second paragraph is spot on. Typically other reagents are used to cross link ( the cellulose in order to retain strength upon getting wet (wet strength). Those reagents are a bit more aggressive. Like alkyl ketene dimer


or urea-formaldehyde polymer.