Given the Mega 2560 has a power jack that takes 7-12v input and regulates it down to 5v, I would say use that. If you were building a Mega clone where you were powering it yourself, then you would have to add a regulator. Depending on how much current your sensor draws, you would either hook up the VIN pin to your sensor, or split the power before it gets to the Mega.
I see that Adafruit has a 9v 1000maH regulated power supply, but I'm sure there are other suppliers as well. http://www.adafruit.com/products/63
If you have a used computer store, they might have a bin where they sell old power supplies. You would bring the Mega to make sure the plug fits (it is a fairly standard size), and check on the specs for voltage (9v) and amps (you would need to add the requirements for the sensor and Mega).
If you want a new regulator, and need it ASAP, you might check your local big box store (Best Buy, Walmart, etc.) or Radio Shack, as they might have appropriate regulators. Radio Shack has this adapter that do multiple volts (3, 4.5, 6, 7.5, 9, and 12) if you might need different voltage amounts for other sensors in the future: http://www.radioshack.com/product/index.jsp?productId=15365586&locale=en_US
If you don't want to do the wiring for splitting the power, Adafruit and other places sell 5.5mm power splitters: http://www.adafruit.com/products/1352. You might need a female plug like: http://www.adafruit.com/products/368 to connect to the sensor, and this male plug if you want to make your own wiring: http://www.adafruit.com/products/369.