Changing out Combination 2 switches!
My hunch is you have 3 cables in this box: 


A /2 cable (black white ground?) which delivers power from the panel
A /2 cable (black white ground?) which carries power onward to other loads
A /3 cable (black white red ground?) which carries switched fan power, switched lamp power, and neutral to the fan. 


Your old switch had two screws which were joined with a "tab", and the tab was NOT broken off.   If the tab is broken off, the screws are totally separate.  If the tab is NOT broken off, then it's a fat 4-way splice, connecting (that side of) both switches, and both attached wires also.  This is confusing, but it's also just what is needed. 

Each switch has power on one side, and on the other side, switched-power to the fan or lamp.  So you make the "one side" the "common" side with the tab not broken off.  

Based on my earlier assumptions, the black wires from both /2 cables go on the "common" side.  

That leaves the red and black from the /3 cable going to the 2 screws on the independent side.