I think what you want is a double pole on-off-on switch. For example: http://www.ebay.com/itm/2-x-3-Way-Design-AC-125V-6A-Double-Pole-DPDT-On-OFF-On-3P-Toggle-Switch-Blue-/121079700806?pt=Guitar_Accessories&hash=item1c30e99d46
The switch has 6 contacts, 3 on one side (A-B-C) and 3 on the other (D-E-F). When it is in the first ON position, A is connected to B and D is connected to E. In the middle OFF position, none of the wires are connected, and in the second ON position C is connected to B, and F is connected to E. As the ebay listing shows, these types of switches are used with electronic guitars, and can have more poles, such as a triple on-off-on switch. Just to be sure, use a circuit tester to make sure there is no connection between the A/B/C side and the D/E/F side, as you don't want to feed 9v into the Arduino.
So you connect the + of the 9v battery to the B terminal. Connect the A and C terminals together, and connect both wires to the + terminal on your 2.1mm power connector. You connect the - terminal of the 9v battery directly to the 2.1mm power connector. Thus when you put the switch into either ON position, power flows to the Arduino.
Then you connect the Arduino ground to the E terminal, and two digital pin inputs (lets say pin 2 and pin 3) to the D and F terminals. If the switch is in the first ON position, pin 2 would indicate a connection (LOW or HIGH depending on if you are using internal pullups or resistors to ground), and pin 3 would be the opposite. If the switch is in the second ON position, pin 2 would be off, and pin 3 would indicate connection. You then control the LEDS as appropriate. Note, you would have to have the switch on long enough while the Arduino determines that it isn't being reprogrammed.
Another way to do it that I know in theory, but I haven't done, is use pins 2 and 3 as the two on switches, and connect them to interrupts when the state changes. Then put the Arduino to sleep. When the contact is made, the Arduino is woken up. While it uses some power, it should use a lot less than normal operation. Nick Gammon covers this is in his power saving tutorial: http://www.gammon.com.au/forum/?id=11497
A third way to do it with a single pole switch, would be have the 9v power feed into an opto-coupler or relay that would be connected to the Arduino pins. I.e. using A/B/C, if A & B are connected, you have a wire that connects to the power, but you also have a shunt to turn on the opto-coupler, and the Arduino would use the other end for digital input. However, I tend to think the double pole on-off-on switch is simpler. With an opto-coupler, you probably want to put in a resistor so that you don't burn out the LED inside of the opto-coupler by feeding it 9v.
A fourth way would probably be a voltage divider and resistor to reduce the 9v to be acceptable to the Arduino. However, I would want to have a better grounding in electrical theory before even attempting it.