How do you choose who to sign up with? Difficult one but most of them will want to give a good service but there will always be one or two that don't... I am quite happy with 123-reg.co.uk at the moment and have been for the last five years or so but in the past have used streamline.net, because they were cheap, and got a 'cheap' service in return (This was some time ago and may well have changed by now though). So the answer is do not necessarily go for the cheapest.
Now you have two recommendations to go on... Good luck.