How do I deal with an automatic reboot following a cydia app install
Well, good news for you. As from a few weeks ago, you are able to jailbreak your iOS 5.1 untethered, which eliminates the fact you've to "just-boot" the iPhone very time.

In order to do so, Jailbreak nation has published a very detailed and good tutorial on how to jailbreak your iPhone. I suggest you preform a untetheredjailbreak and try again. If things are still not working, please give some feedback with your errors so we can help you further.
Good luck!