You wanna think of this in terms of what's happening with electrons at each electrode. Oxidation occurs at the anode, so negative electrons are being stripped off an atom and moving to the positive anode. At the Cathode, electrons are moving from the electrode to the positive cations, reducing them. So the anode is positive, the cathode is negative.
The terminals in circuits are actually the wrong way round (against what you think they should be), but it was an arbitrary choice before we knew whether electrons were negative or positive (which is also arbitrary really.) We could change it now, but that would mean changing ever battery/electrode in the world!