How do I recover a deleted world in Minecraft Xbox?

If you explicitly deleted your world, and do not have a manual backup, you are out of luck.

Theoretically, you could remove the HDD from your 360, insert it into a PC (since it should be formatted in FAT32), and use file recovery software to attempt to recover the save. However, there is no guarantee that the world could be recovered using that technique, and you could potentially damage your console/HDD if you don't know what you're doing.