Melons currently (version 1.6.4) do not grow naturally in Minecraft. This means that you will have to get them by trading with the villagers or by searching the chests of abandoned mines. Once you have melon seeds, you can plant them, grow them and create your own seeds!
Steps
Method 1 of 3: Abandoned Mines
You will be able to find abandoned mines deep inside, and it will be easier to discover them when they intersect with caves and ravines.
Step 1. Choose a deep cave or ravine to explore
-
Make sure you are well prepared, as abandoned mines are dangerous in all modes except Pacifica.
Find Melon Seeds in Minecraft Step 1Bullet1

Step 2. Explore until you find wooden rails, poles and fences, or torches that you didn't set up


Step 3. Explore the mine until you find a chest

Step 4. Each crate has a chance of containing melon seeds
Method 2 of 3: Trade
Farmers living in villages can offer you melon slices for an emerald, and by breaking the slices you can get the seeds. You can find emeralds by digging in the extreme hills biome.

Step 1. Find a village
Step 2. Find a farmer
-
The peasants wear simple brown robes.
Find Melon Seeds in Minecraft Step 6Bullet1

Step 3. Right click on a farmer to offer a trade
-
If the farmer doesn't offer you melon slices, you may need to find another farmer!
Find Melon Seeds in Minecraft Step 7Bullet1

Step 4. If you have any melon slices, drag the emerald into the swap field, and drag the slice into your inventory

Step 5. Put the melon slices in the crafting menu, and drag the seeds to the inventory
Method 3 of 3: Grow Your Own Melons
When you have at least one melon seed, you can start a farm. Melons grow on cropland near water, but they need a clear block above the roots and a free one next to the roots to grow.

Step 1. Create (or find) an irrigated farmland

Step 2. Make sure you leave a clear block over the roots (air or glass)

Step 3. Plant the melon seeds

Step 4. Wait for a melon to grow

Step 5. Once you have a melon, you can break it into slices
You can eat them or put them on the crafting grid to get more seeds.
Advice
- Villages are created only in flat biomes (desert, plain, savannah).
- Be careful when exploring abandoned mines. Spiders, ravines and monsters that arise in the dark are real dangers, and you risk getting lost.
- If no farmer offers you the trade you want, you can get new ones by completing the offers they make to you.