How high of a baud rate can I go (without errors)?
There are several factors here:


How high of a baud-rate can the ATmega328P MCU achieve?
How high of a baud-rate can the USB-Serial interface achieve?
What is the oscillator frequency on the ATmega328P?
What is the oscillator frequency on the USB-serial interface (if it has one)?
How tolerant is the USB-serial interface of baud-rate mismatch?


All of these factors are relevant to determining the maximum achieveable baud rate. The ATmega328P uses a hardware divisor from it's clock-rate to generate the base-clock for the serial interface. If there is no integer ratio from the main clock to the bit-time of the desired baud rate, the MCU will not be able to exactly produce the desired rate. This can lead to potential issues, as some devices are much more sensitive to baud-rate mismatch then others.

FTDI-based interfaces are quite tolerant of baud-rate mismatch, up to several percent error. However, I have worked with specialized embedded GPS modules that were unable to handle even a 0.5% baud rate error.

General serial interfaces are tolerant of ~5% baud-rate error. However, since each end can be off, a more common spec is +-2.5%. This way, if one end is 2.5% fast, and the other is 2.5% slow, your overall error is still only 5%.



Anyways. The Uno uses a ATmega328P as the primary MCU, and a ATmega16U2 as the USB-serial interface. We're also fortunate here in that both these MCUs use similar harware USARTs, as well as 16 Mhz clocks. 

Since both MCUs have the same harware and clock-rate, they'll both have the same baud-rate error in the same direction, so we can functionally ignore the baud error issue.

Anyways, the "proper" answer to this question would involve digging up the source for the ATmega16U2, and working out the possible baud-rates from there, but since I'm lazy, I figure simple, empirical testing will work.

A quick glance at the ATmega328P datasheet produces the following table:


So given the max stated baud-rate of 2 Mbps, I wrote a quick test program:  

void setup(){};

void loop()
{

  delay(1000);
  Serial.begin(57600);
  Serial.println("\r\rBaud-rate = 57600");
  delay(1000);
  Serial.begin(76800);
  Serial.println("\r\rBaud-rate = 76800");
  delay(1000);
  Serial.begin(115200);
  Serial.println("\r\rBaud-rate = 115200");
  delay(1000);
  Serial.begin(230400);
  Serial.println("\r\rBaud-rate = 230400");
  delay(1000);
  Serial.begin(250000);
  Serial.println("\r\rBaud-rate = 250000");
  delay(1000);
  Serial.begin(500000);
  Serial.println("\r\rBaud-rate = 500000");
  delay(1000);
  Serial.begin(1000000);
  Serial.println("\r\rBaud-rate = 1000000");
  delay(1000);
  Serial.begin(2000000);
  Serial.println("\r\rBaud-rate = 2000000");
};


And then looking at the relevant serial port with a serial terminal:  



So it appears the hardware can run at 2,000,000 baud without problems.

Note that this baud rate only gives the MCU 64 80 clock-cycles per byte, so it would be very challenging to keep the serial interface busy. While the individual bytes may be transferred very rapidly, there is likely to be lots of time when the interface is simply idle.



Edit: Actual Testing!

The 2 Mbps is real:

each bit-time is 500 ns, which matches exactly with what is expected.

Performance issues! Overall packet length:
500 Kbaud:


1 Mbaud:


2 Mbaud:

Note: The noticeable overshoot is due to poor scope probe grounding practices, and is probably not real. I'm using the ground-clip-lead that's part of my scope probe, and the lead-inductance is likely the cause of the majority of the overshoot.

As you can see, the overall transmission length is the same for 0.5, 1 and 2 Mbaud. This is because the code that is placing the bytes in the serial buffer is poorly optimized. As such, you will never achieve anything better then an effective 500 Kbaud, unless you write your own serial libraries. The Arduino libraries are very poorly optimized, so it probably wouldn't be too hard to get a proper 2 Mbaud, at least for burst transmissions, if you spent a bit of time on it.