I am looking to use my Uno to control a fan via bluetooth from my android phone.
The simplest way would be to use the phone to push the switch on the fan. No software required.
Since that is probably not what you want to do, you need to be a lot more specific about what control you expect to have over the fan. Turning it on or off can be done with a relay or a mosfet. Making the fan run at different speeds can not be done with a relay.
Can I use a 12VDC fan and have an external power supply to the fan?
Not only can you, you must.