Some friends and I were under the impression that iCloud does not back up Apple Health data, partly due to privacy reasons. This Apple support doc (which looks more like a product page) also states as such.
But I recently wiped my iPhone for reasons, restored from iCloud backup, and my Health data came along for the ride. I did some more digging, and found this support doc, last edited June 11, 2015, which states iCloud does back up Health data.
From talking to a couple others, they also confirm Health data restored from iCloud back up. Maybe that first Apple doc simply needs an update.