I am only 5 days into my Billing cycle, and noticed that already like 1/3rd of my data has been used (thanks to My Data Manager)... So I looked to see what has used all this data, and it says it is "Media Storage" that has used up most of my data (it's used up over 35 MB!). This is a system process if i'm not mistaken, so my question is: is this in fact a system process? And why would it be using up so much of my data? What exactly does this process do? Would it be safe to deny it network access?
Yes, it's a system process. Other apps may use Media Storage to download, play, and stream audio/video. I don't know specifically which media apps actually uses them though. You might try to block it, and see if any functionalities in the media player you regularly uses stops working.