Mezzanine is Django. Search for django hosting best practices.
I use AWS. Heroku works fine. Appsembler has hosting specifically for Mezzanine. Rackspace, nee slicehost, is good. Steer clear of shared hosting! There lies madness.
Mezzanine's fabfile deploys cleanly to every Debian-like GNU/Linux I have tried. Other platforms and configurations (apache, mysql, etc vs the stock nginx, postgres stack) definitely work, but will require more manual effort and brings the frustration that comes from non-automated solutions.