The main issue will be in handling ethernet packets rather than hardware interfacing, plus the overhead of initialising the device. On the hardware front, I'd recommend buying a ready-build board which includes magnetics and everything else. Google should turn up a few options, SparkFun's, Packet Whacker etc.
Difficulty; I'd say medium to hard, but depends on what SPI skills you have, what you know about TCP/IP protocols and your tolerance for extensive reading of datasheets and general perseverance. I wouldn't start with anything less than an 18X. There's plenty of example code out there but it would need porting to the PICAXE.
Alternatives are PICAXE.Net, SimpleLan, SitePlayer, NEMO10, the XPORT range and probably others I've forgotten which are more than just the bare-bones hardware.
PICAXE users have used the SimpleLan so a forum search is in order there.
There's also the Linksys NSLU2 ( "NetSlug" ) and routers which can be re-purposed as Ethernet to serial port ( and thus PICAXE ) bridges, and of course a PC can do that.
Best choice rests on what you ultimately want to achieve, how easy you want to do the job, how much time and frustration you're prepared to invest, plus how much money you're prepared to spend. If you want it cheap and choose the ENC28J60 you have to expect a lot more work to get it going.
