How to use FETs to switch supplies in circuit
What kind of battery?  You can get power controllers for lithium cells that take care of all the problems, charging the cell and switching between USB and battery power.

eg http://www.sparkfun.com/products/726

If you wanted to do it yourself, you could use two MOSFETs (which can be thought of as a transistor with very low resistance when turned on), one controlling each power connection.   Pull the gate input up with a resistor on the battery, so that the power defaults to battery.  

By connecting the mosfet gates to tri-state output ports on a microcontroller, it can it can choose which power supply to use once it has booted, overriding the pull-up/pull-down resistors.

This is likely to be very tricky.  The more usual approach is to have the external power charge the battery, possibly using a step-up converter.