After going on a general exploratory mission that uncovers new land I use Cartograph to highlight pumpkin blocks on my map, and then go track them down on foot. They're pretty rare, so it takes a lot of walking.
This first time I ever played Minecraft, I found three pumpkins within the first 60 seconds. I lost them after death, but within the same game I found a patch of a dozen or so. In both cases they were found in heavily forested areas, clustered around tree trunks. The first, smaller, pumpkin patch was at the top of a forested cliff, the second larger patch was slightly above sea-level.