According to the software's developer in this document:
Lion is recommended. VMWare Fusion is a mature and well-respected product. If you need Windows, go for it.
Lucky for you, Ars Technica just published an extremely detailed review of how VMware runs in Lion, in a comparison to Parallels Desktop. Ars Technica does some of the best reviews around.