For a device that transmits continuously (like a GPS) I've found the easiest way to detect the baud rate is to simply try each possibility until something recognizable arrives. If the baud rates are tested in a logical order (e.g. 4800 first) then, in most cases, the detection takes just a few frames. On success, saving the baud rate to EEPROM makes detection even faster the next time around.