Deepholm is the reason I chose Cataclysm as my timeline. Now I’m not sure if Deepholm is in Cataclysm or not… because I’m kind of lost and thought I’d get sent there the moment I picked this expansion from Chromie.
What’s up guys? Because I’ve been sent to the Wetlands, and now Arathi Highlands instead. 
Cataclysm includes the vanilla zones. All the Cata zones are 30-50 with Chromie Time active, so from 1-30 you level up in the old zones (or a different expansion).
As a bit of an explanation, the old 80-85 Cataclysm zones were built around the assumption you have flying, so to get around that, they just set their minimum level to the level when you unlock flying. (Cataclysm was the only expansion where you could fly right from the start — all others either required max or near max level to originally unlock, or a pathfinder achievement.)
Ah okay… so now… when can I go to Deepholm, please?
What do I need to do to get there? What level do I need to be, etc?
Level 30.
I don’t think there’s any other requirements. As Udiza said, you should purchase flying before you go, otherwise you’re going to have trouble getting around down there (and some parts of it might be completely inaccessible).
There’s an island just northwest of Stormwind Keep with portals to all the Cataclysm zones on it. AFAIK, that’s the only way to get to Deepholm (the other Cata zones can be traveled to by more conventional means in addition to the portals).