I agree with Barry - try your best to get untethered as they are much easier to use. Basically you need a box that does NOT have the latest software on it - 5.01 - otherwise it cannot be jailbroken untethered. Basically it means when you switch the apple tv off (remove the power cord or switch off at the socket)you will have to connect to a laptop or pc to boot it up again. An untethered one does not have this problem.
I expect a 'crack' for 5.01 will be available soon which means anyone with a tethered box should be able to re-jailbreak as soon as it's ready.