If the shield uses SPI, it will NOT work out of the box on the Mega, since it has the SPI spins in a different physical location.
You can either choose to do a hardware hack (reroute the pins) or do software SPI which is slower (in terms of transfer speed between the Arduino and ethernet shield) but should work just fine. Here's a software hack I did to get an LCD shield working in this way:
My advice is to check the software that comes with the ethernet shield and check if it uses SPI. If it does, either find a shield that is verified to work with the mega, or be prepared to do some hacking to get it to work.
The ENC26J80 definitely does use SPI. If you do a google search forarduino mega ethernet shield hack you'll get some useful info on how people have dealt with the SPI incompatibility between the "standard" Arduino and the Mega.
There's also a link to a shield tweaked for the Mega that uses the standard Ethernet library. I'm a fan of NKC: I've bought from them 4 or 5 times, and always gotten excellent service at prices that were at least "good" (even by my cheapskate standards), and sometimes even "super".
Unless you're painfully broke, I suggest spending the extra bucks to get the Mega-friendly shield.
btw, I personally have the Adafruit shields, and have been very happy with their performance on my non-Mega Arduinos. Because of their design (extra pads on the connector holes), it may be possible to do the same sort of tweak for the Mega. I definitely found the extra holes handy when I needed to connect a small number of wires for sensors: I just soldered them directly to the shield, instead of needing a proto shield or other extra parts.