The main thing you need to get right for HA to work is name resolution.
Almost all errors relating to HA are down to name resolution.
Ensure each server can see the same storage and bobs ya uncle.
The following are requirements for running HA.
Centralised licensing must be use for HA in all environments. You can not use host based license files.
Virtual machine must reside on share storage (NAS, iSCSI and FC are all supported).
The physical networks required by the virtual machines must be available to each host and the vSwitch(s) must have the same name on each host.
HA is a licensed feature of VI3. HA is included in both the VI Standard and VI Enterprise license. You can not use VMware Server to provide HA.
HA is an additive feature to 3i.
Also ensure you have good networking setup, have a redundancy in your console network. Consider changing some of the isolation paramaters, expecially the isolation response to leave running (its a global setting in 3.5 which is nice).
The document you want to read is http://www.vmware.com/files/pdf/VMwareHA_twp.pdf
Considering awarding points if this is of use
What are the symptoms you're seeing? (or not seeing?) What are the conditions you're testing HA under?
You seem concerned that HA might need VMotion to work (which, as it has been pointed out, it doesn't) - does this imply that VMotion is not currently working in your environment?
One issue I had getting mine to work is that a previous net admin had disabled the ability to ping the default gateway. HA did not like this one bit, as it pings the default gateway to determine whether it has connectivity.
If you found this or any other post helpful please consider the use of the Helpfull/Correct buttons to award points