It’s from “brigantine”, a kind of two-masted vessel. Originally the abbreviate referred to the vessel, but from about 1850 it came to refer also to a naval prison, and later to a military prison. A brigantine was a fairly small vessel, and - wild guess - possibly the prison was called a “brig” because of the confined space it offered.
In due course “brig” stopped being applied to the vessel, and came to refer exclusively to the prison.