A brace usually refers to a brace of pheasant or some other game, brace being another word for a pair. To bag a brace means that you have shot a brace to take home in your game bag.
I was always told to bag a brace was the term used when a shooter bagged (shot) a pair (brace) of birds from one flight with single shots from each barrel of a shotgun