Need to receive an alert when a Linux server reboots. How can this rule/monitor be created?

You can use the "Shell Command" templates to create a UNIX/Linux Shell Command (Alert) rule.  See the walkthrough and background here: http://operatingquadrant.com/2012/01/30/opsmgr-2012-unixlinux-authoring-templates-shell-command/

The following command will identify the seconds the system has been "up" and return OK if it is greater than 15 minutes, and REBOOTED if the seconds up are less than 15 minutes.  Your Shell Command rule should alert if the StdOut value contains REBOOTED. 

upseconds=`cat /proc/uptime |awk '{print int ($1 )}'`;if [ $upseconds -lt 900 ];then echo REBOOTED;else echo OK;fi