How to set Apple Magic Mouse permanently with Mac?
You shouldn't have to continually pair the mouse after every restart, this indicates there is a problem.

First thing I would try is to power everything down, and then turn the mouse back on (small switch on the bottom) so that the mouse is "discoverable" before restarting. Ensure you follow these set up instructions after restart.

Make sure you have installed all system updates. OS X 10.6.2, for example, fixed a problem with bluetooth pairing.

If this still doesn't fix the problem, you could try to Reset the System Management Controller (SMC) (see this Apple support document.)