Here's my experience in building HA in Linux. There are two key pieces: storage replication and failure detection. Replication is so that there's a standby system with the same persistent state ready to go, and failure detection, well, the whole point of HA is to ensure ongoing operation to continue in case of failure.
For storage replication, Linux has the excellent DRBD (http://www.drbd.org/) software to replicate disk at the block device level. This is great because any kind of disk based systems can be supported, such as database server, mail server, file server, DNS server, etc.
For failure detection, Linux has the Linux HA Heartbeat ( http://www.linux-ha.org/wiki/Heartbeat). This would detect failure at machine level and ensure proper failover.
Within a machine, there are other tools to monitor process level failure and propagate the failure to Linux HA Heartbeat.
BTW, STONITH is a super simple way to avoid the partition problem.