Is your Arduino a standard unit with a standard linear reg or do you have a Freetronics which has a more effective switch mode reg?
You have a multimeter right?
How are you powering the Arduino, with external power supply, or are you using USB power from your computer?
Unplug your power supply and check the voltage of your power supply going into the Arduino, unplugged.
If you use an external supply, it needs to be within spec. Max is typically 24 vdc.
If you are using usb cable, it too needs to be within spec, and this is 5 volts dc.
If the above checks out proceed to next step below,
Remove any I/O devices you have connected to your board, that is, remove all wires.
Plug your power supply cable into your Arduino,
If using external supply
check the voltage of the Vin pin, it should be the same reading as you read before.
Next, check the output voltage of your onboard regulator, you should read 5 volts all being well.
If it is significantly greater than 5 volts dc, remove power supply and replace regulator.
If voltage is 5 volts dc, and board is cool, and you removed some wires for I/O, then suspect your I/O or the way you are using your I/O ports, check software.
Try loading a simple blink program, dos it still get hot?
If you are using USB power,
You potentially have an issue with the electronics on the Arduino.