What you need is a single pole double throw (SPDT) switch.
The circuit looks like this:
<!-- Begin schematic: In order to preserve an editable schematic, please
don't edit this section directly.
Click the "edit" link below the image in the preview instead. -->
<!-- End schematic -->
One LED will **always** be turned on.
The resistors are **not** optional. You must have them to keep the LEDs from burning out. There are plenty of posts on this site about calculating the resistor values given the battery voltage, the LED forward voltage, and the LED current - I'm not going to go into that here.
The resistors are useful for a second reason, as well.
Red and green LEDs don't light equally bright for the same current. With separate resistors, you can tweak the current to make the LEDs approximately equally bright.