Where should they spawn?

All variants of Jungles. (Mini Jungle, Vanilla if possible) and Temperate Rainforest?

Don't make them to common though. Having melons have a decent rarity is nice.

Per @TheEnlightened from the forum.

Ah, this sort of breaks the fact that melon seeds are only found in strongholds,
but i do like this idea, i think you should just add the melon spawns as sort of a
hitchhiker to the pumpkin spawns, making them spawn 50/50.

Unless your refer to actual farms in that case mushroom, plain, and forest biomes.

Hmm...melon farms?

Now there is an idea...

Well a melon can grow in pretty temperate zones if you think about it but from know how in growing them, they like warmer weather, so biomes that have generally warmer climate come to mind, though the desert I think would be way to warm for it.

I've also found melon seeds in dungeons or are those considered strongholds?

You are right melons are found in the tropics...they abound here where I live! But...Mojang has made them a pretty special item and rare for game balance...

Here is what I am thinking: When a village generates in a hotter climate it has a 1/1000 chance of containing a melon farm...

Will that keep it rare enough to maintain balance?

That would seem reasonable to me though a 10/1000 chance would seem better to use. I mean 1-1000 is a large margin after all :D like sifting through a million grains of sand for that one tiny bit of gold nugget

OK...the chance to find will be configurable.

I like configurable with a default of 1/100 chance to spawn a melon farm in the village.

OK...so the real chance of a melon spawn is (villageProbability) x (melonProbablilty)

I do agree that they should be found on the map -- the seeds in the chests had to come from somewhere.

Remember, cocoa beans used to be chest only; now they are tree common.

There is no justifiable reason I can think of to make them dungeon only. Village farms make sense. As does randomly in patches in the wild.

I wouldn't mind villages getting melon farms, but I would think they should get pumpkin farms as well.

http://i1178.photobucket.com/albums/x361/AndrewSupertrampHolley/2012-08-04_142707.png

And as for wild melon patches, I think finding them half as often as pumpkin patches would work. Still a little rarity but possible to start a farm if you don't want to go dungeon diving.

Agreed.