We present the results of a near-infrared monitoring program of the Anomalous X-ray Pulsar 1E 2259+586, performed at the Gemini Observatory. This program began three days after the pulsars 2002 June outburst, and spans ~1.5 years. We find that after an initial increase associated with the outburst, the near-infrared flux decreased continually and reached the pre-burst quiescent level after about one year. We compare both the near-infrared flux enhancement and its decay to those of the X-ray afterglow, and find them to be remarkably consistent. Fitting simple power laws to the RXTE pulsed flux and near-infrared data for t>1 day post-burst, we find the following decay indices: alpha=-0.21+/-0.01 (X-ray), alpha=-0.21+/-0.02 (near-infrared), where flux is a function of time such that F is proportional to t^alpha. This suggests that the enhanced infrared and X-ray fluxes have a physical link post-outburst, most likely from the neutron-star magnetosphere.