There are various ways for doing autotuning. Basicallly you step the setpoint and analyze the system response regarding risetime, overshoot, amplitude and frequency of any oscillation and so on.
I've got the question before and did some research into the matter but to be honest the math involved is beyond me. Right now I re-Googled PID Autotune and it came up with a link to a autotune library for Arduino - I may need to have a look at that!

If you're up for it, feel free to take a stab at it!

/Henrik.