Correct DC Adapter type to use for Arduino
You can find some documentation related to this on the Arduino Website here:
http://arduino.cc/en/Main/ArduinoBoardDuemilanove

Essentially.. the thing to know is that it is a 7805 regulator.. any excess voltage is being converted into heat.  The Arduino runs at 5V.. and in order for the regulator to work it needs to be a minimum of around 1.5 volts above that.. so your "Minimum" is about 6.5V DC.  

You want to try be as close to that as possible - so 7.5 and 9 volts DC are fine .. you can run at 12 volts DC.. but the regulator will get a little warm.. and I wouldn't do this if you are powering much from the Arduino board as that will increase the heat output.

The bottom line: 7.5V DC is best, 9V and 12V DC are OK.  Anything about 12V is probably pushing it.  12V is the most common you will find "lying around".

The Arduino uses a Barrel-style connector .. it is compatible with most reasonably sized plugpacks.. I am not sure what the size in millimeters is.