We present the results of a search for the effects of large extra spatial dimensions in p collisions at =1.96 TeV in events containing a pair of energetic muons. The data correspond to 246 pb-1 of integrated luminosity collected by the D0 experiment at the Fermilab Tevatron Collider. Good agreement with the expected background was found, yielding no evidence for large extra dimensions. We set 95% C.L. lower limits on the fundamental Planck scale between 0.85 and 1.27 TeV within several formalisms. These are the most stringent limits achieved in the dimuon channel to date.