I once had a similar problem with a microcontroller which didn't have a UART nor exactly known clock frequency (crystal was too expensive).
I let the other party send a specific byte, for instance 0x01 and measured the time the bus was low. This was 8 bit times (startbit + 7 zeros of data). So dividing this by 8 I got the value I should set my timer to.
So, before you configure the I/O pins for UART use them as common I/O until the Bluetooth module sent this agreed upon character and time it. You could do this running a loop, or use timer capture to detect the falling and rising edges (more accurate).
To understand all of this stuff, take a look at "Table 18-1. Equations for Calculating Baud Rate Register Setting" from the datasheet on page 189. The equation you suggested you found in some example code
UBRR1 = (F_CPU / 4 / baud - 1) / 2;
... is kind of close to the equation for Asynchronous Double Speed mode (U2Xn = 1)... but not exactly.
If you know the baud rate and crystal speed you intend to operate at, I would just pull the register settings out of "Table 18-9. Examples of UBRRn Settings for Commonly Used Oscillator Frequencies" on datasheet page 210 and call it a day. The only reason to use any of those equations is if you want to be able to change the settings dynamically at run-time for some reason (or if you want to do thins "elegantly" in software, I prefer compile time certainty for something like this to remove doubt).
For the settings you outlined in your question, that would be:
UCSR1A = 0; // importantly U2X1 = 0
UCSR1B = 0; // interrupts enabled in here if you like
UCSR1C = _BV(UCSZ11) | _BV(UCSZ10); // no parity, 8 data bits, 1 stop bit
UCSR1D = 0; // no cts, no rts
UBRR1 = 103; // 9600 baud @ 16MHz XTAL with U2X1 = 0
As a side note, while the hardware does store the baud rate register (UBBRn) as two 8-bit registers, in software there is no need to treat it as such. You can access the High and Low registers (e.g. UBRR1H and UBRR1L respectively) but you can also just
assign to (or read from) the named "combined" register as though it was a 16-bit register.
UBRR1 = 0x0343; is functionally equivalent to UBRR1H = 0x03; UBRR1L = 0x43;
Best Answer
To change the Baud rate on the BlueSmirf, you will need to enter Command mode. To enter Command mode, you need to send "$$$" through the serial port connection. This can be done from a PC using a terminal program or from the Arduino.
Since you want to do this from the Arduino, you will need to write a little bit of code to parse the responses from the BlueSmirf so you can automate the steps necessary to change the Baud rate.
All the commands are documented in the RN-42 AT Command Set