Dogberry:
Arduino Micro powered by 9V battery
Very bad idea. Use a proper 9v wall wart. Maybe connect bluetooth to your phone instead, i.e. just use the USB to provide power.
I assume the bluetooth is 115400 by default. If not, be sure the code matches the speed properly.
TX (pin 0) on arduino micro -> RX on Bluetooth Mate
RX (pin 1) on arduino micro -> TX on Bluetooth Mate
Most Arduinos have Tx on pin 1