I came up with the following circuit that does what you ask:
5 volts from the "SWITCH" source will turn on M1 and M2, connecting the 3 volt rail to the load, and pulling current out of the right hand transistor of the differential pair Q3 and Q4. This turns off Q2 and shuts down the 5 volt rail. When Q1 turns off by applying 0 volts to "SWITCH", Q4 is biased on by the voltage divider comprised of R7 and R8, which turns on Q2 and the 5 volt rail. R2 then pulls up the gates of M2 and M1, shutting the 3 volt rail off. The arrangement of M1 and M2 prevents conduction from the 5 volt rail into the 3 volt rail when the 5 volt rail is connected.
In a real circuit there should probably be stopper resistors on the MOSFET gates.
Another way, in response to the "too many components" criticism:
If you don't want to use discretes, you can do it with a cross-coupled dual comparator. One IC and 4 resistors, plus the switches.