What package? Altera does a pretty good job at supplying app notes for decoupling. Have you looked around on the website?
You are not running very fast at 40MHz. Are you planning on using any PLL's? On the BGA packages the VCCINT pins are typically all located in the center of the chip. Use 0402 package ceramic capacitors, something like a 0.01uF and 0.001uF (1000pf) pair for every couple of VCCINT pins or whatever you can reasonably pack in underneath the center of the FPGA should suffice for your needs.
Throw a couple of 20uF bulk Tantalum caps outside near the perimeters of chip.
Rob