How do I wire a double stack switch?
Not knowing which brand you are using, I just googled double stacked switches, saw the Leviton 5224-2W and noticed the black screws are for the switch legs going to each light while the brass screws are for the hot common, which are typically bridged together with a removable fin (or "tab" as Brad Gilbert mentioned). If the fin has been removed, you will have to create a bridge with wire to feed both switches. When connecting, use the brass screw(s) for the constant hot and the black screws for the independent switch legs. If the connections are mis-arranged on the switch you would have the issue as you describe.

In pictorial form, if you have this:


You'll need to do this instead:

The Black and White coming in from the bottom would represent your hot/neutral feed at the switch. This is assuming some things, as your feed could just as well come in at one of the lights. A few pictures from your end would help if this does not look like what you have.