We study magnetohydrodynamic (MHD) effects arising in the collapse of magnetized, rotating, massive stellar cores to proto-neutron stars (PNSs). We perform axisymmetric numerical simulations in full general relativity with a hybrid equation of state. The formation and early evolution of a PNS are followed with a grid of 2500x2500 zones, which provides better resolution than in previous (Newtonian) studies. We confirm that significant differential rotation results even when the rotation of the progenitor is initially uniform. Consequently, the magnetic field is amplified both by magnetic winding and the magnetorotational instability (MRI). Even if the magnetic energy E-EM is much smaller than the rotational kinetic energy T-rot at the time of PNS formation, the ratio E-EM/T-rot increases to 0.1-0.2 by the magnetic winding. Following PNS formation, MHD outflows lead to losses of rest mass, energy, and angular momentum from the system. The earliest outflow is produced primarily by the increasing magnetic stress caused by magnetic winding. The MRI amplifies the poloidal field and increases the magnetic stress, causing further angular momentum transport and helping to drive the outflow. After the magnetic field saturates, a nearly stationary, collimated magnetic field forms near the rotation axis and a Blandford-Payne-type outflow develops along the field lines. These outflows remove angular momentum from the PNS at a rate given by J similar to eta EEMCB, where eta is a constant of order similar to 0.1 and C-B is a typical ratio of poloidal to toroidal field strength. As a result, the rotation period quickly increases for a strongly magnetized PNS until the degree of differential rotation decreases. Our simulations suggest that rapidly rotating, magnetized PNSs may not give rise to rapidly rotating neutron stars.