<a href=”http://www.wisesolutions.com/Products/Packaging/Overview.aspx”>WISE</a> makes several flavors of these type tools… from a stripped down single purpose tool to a (almost) everything but the kitchen sink version, except is is focused specifically on what you are wanting. (On a side note, It looks like they were recently purchased by symantec– hasn’t everybody?)
This tool is the Cadillac of packaging tools, others may know cheaper solutions and I’ll look to them to add them in this answer. However, WISE has been doing this for some time and generally is the bar by which all others are measured.
Now, for the reboots. In general, if the installation modifies HKey Local machine, a reboot will likely be more probably, since a system only reads that at startup and copies it into HKey_System and HK_Current_Config. However, you may get away from a few reboots– though every software manufacturer will point you to a reboot the moment you call for support and they find out one hasn’t taken place after installation.
Another alternative to WISE, if you have SMS installed on your network, is the SMS Installer. I’ve not worked with the newer versions since 2.0, but I assume they have something similar that lets you create a MSI package to install the software from.
They all work on the same principle. Snap shot the registry and file system, install software, snapshot teh registry and filesystem— then make a executable file containing the differences to recreate the installation.
I hope this helps you.