They are a "step" family because Mike and Carol Brady combined their children from their first marriages.
The only real backstory that we get from Mike's first wife is that she died. Mike makes the comment about not wanting Bobby to forget his Mother. There is even a photo of her in the first episode.
Mike - Where’s your mother’s picture Bobby?
Bobby – I put it away. In the drawer.
Mike – Because of Carol?
Bobby – I thought she might not like it when she moves in.
Mike – Come here Bobby. Now you can put it right back son.
Bobby – Are you sure?
Mike – I’m positive. I don’t want you to forget your mother. And
neither does Carol.
Bobby – Gee, that’s swell. I really like this picture, but I didn’t
want to upset my new mom.
Mike – You know something? Your mother be very proud of you right now.
Wikipedia also states that Mike Brady was a widower:
Mike Brady (Robert Reed), a widowed architect with three sons, Greg
(Barry Williams), Peter (Christopher Knight), and Bobby (Mike
Lookinland), marries Carol Martin (Florence Henderson), who herself
has three daughters: Marcia (Maureen McCormick), Jan (Eve Plumb), and
Cindy (Susan Olsen). The wife and daughters take the Brady surname.
It is never revealed or mentioned in the television show what happened to Carol Brady's first husband.
Sherwood Schwartz kept the status of Carol's first marriage a secret:
Mike's first wife had died, making him a widower, but the status of
Carol's first marriage was kept a secret. Creator, Sherwood Schwartz
maintains Carol was divorced from her first husband, but nothing about
it was mentioned on the series. At that time, divorce was a subject
matter that was still considered largely taboo for television,
particularly a series aimed at family audiences.
There was a 1996 movie titled A Very Brady Sequel. This movie's plot is centered around Carol Brady's first husband:
One evening, a man claiming to be Carol's long-lost first husband, Roy
Martin, shows up at the suburban Brady residence. He is actually a con
man named Trevor Thomas and is there to steal their familiar horse
statue that is actually a $20 million ancient artifact. They,
portrayed as naïve, believe his story about suffering from amnesia and
having plastic surgery after being injured. Throughout Trevor's stay,
he is openly hostile to them, his sarcasm and insults completely going
over their heads. Bobby and Cindy start a "Detective Agency" hunting
down her missing doll and stumble upon Trevor's true intentions.
Trevor kidnaps Carol and takes her and the artifact to a buyer in
Hawaii. The remaining Brady family travels to Hawaii to save her and
foil his plans.
It is revealed at the end of the movie that Carol's first husband actually died at sea on an expedition.
This is not discussed in the original television series.
The plot of this movie is based on the idea that the fate of Carol's
first husband is never mentioned in the original TV series. In the
series pilot, it is implied that Mr. Brady's first wife is deceased.
NOTE: There is no evidence that the plot of this film informs audiences about what actually happened to Carol's first husband in the television series. The mention of this film is merely a side note to the answer.