Horned Melons can be found on Jungle floors.
Melons can be eaten directly to grant player characters a little Stamina-maximum bonus, they can be fed to Pets (some prefer Melons as their favorite fodder) and/or can be used used to make Food like Melon Pie (grants poison resistance and +100 max. Stamina and is the favorite food of a number of Pets) or Melon Sandwiches (these will grant +200 max. Health and +100 max. Stamina) in the Cooking Station.
Melons are quite rare at first, but the longer you play on a Creativerse world the more of those will spawn. If players are staying somewhere close to jungles this seems to increase the chances of Melons spawning. Sleeping on a Bed to skip day or night will not help speeding up this process though.
Unfortunately for now it seems that Melons cannot be made to spawn in artificial "jungles" made from Detritus, so to collect your first Melon you will have to explore the Creativerse Worlds a bit to find Jungles and cross these biomes a few times until Melons will spawn there.
You can use your Map and compare it with the maps of template worlds ( http://steamcommunity.com/sharedfiles/filedetails/?id=634088783 ) to see where the closest jungle might be. Also Savannahs and Swamplands are often direct neighbours of Jungles, so try encircling those biomes.