Mine underground around a bit, and if you hear zombie or skeleton noises, you have either found a dungeon or a cave. Mine around, and if you see mossy cobblestone, you have found a dungeon. Mine through the wall and you are in!
Melon seeds can also be found in mineshafts, which are found deep underground.
Mellon seeds are obtained through the Nether Reactor which is pretty costy. You need a total of 3 diamonds, 6 iron ingots, 36 gold ingots, and 14 cobblestone to make it. Once you activate the nether reactor, it will spawn a rather large obsidian oblisk, then it will spawn between 5 - 10 zombie pigman along with random items in different amounts. After about 30 seconds, holes will appear in the sides of the oblisk and the reactor will turn into obsidian. This is currently the only way to obtain mellon seeds, however the developers may change this in a future update.