Cut the fat first. It will give you some perspective on how much muscle you actually carry, and will better prepare your body (for example, by improving your muscles' sensitivity to carbs) for when the time comes to increase calories and "bulk".
Changes are much easier to track when your starting point is a lean physique. It's much easier to notice when increases in bodyweight are excessive relative to the amount of strength you are gaining. Negative effects of "bulking" (I hate that term) can be remedied before they get out of control.
My personal opinion is that it should be possible to gain plenty of strength and muscle, while keeping bodyfat under 12% (approx.).
Your current fat mass is too high, in my opinion, to consider a mass gaining phase. You'll probably end up uncomfortably fat, and any subsequent cut will be no fun at all.
As others have mentioned, a full-blown cut probably isn't necessary yet, but rather you should eat mostly whole foods, track calories (absolutely essential I believe), and work your ass off in the gym. Barbell complexes would probably be a good place to start, depending on how much bar control you have.
This advice comes from personal experience. Being fat is horrible, and unnecessary.