a few thoughts:
* do they look likely to stay in business?
* how good is the support?
* who provides DNS, you or them?
* hidden costs, e.g. they charge you if you want to transfer the domain to another registrar, they charge you if you want to manage your own DNS, they charge you if you want web forwarding...
* you might want to register the domain with the same firm that runs your web hosting and email, it can make life simpler if you only have to deal with one company.