We analyze experimentally and theoretically the sound propagation velocity of P-waves in granular media made of micrometer-size magnetite particles under an external magnetic field. The sound velocity is measured in a coherent (long-wavelength) regime of propagation after a controlled sample preparation consisting of a fluidization and the application of a magnetic field. Several different procedures are applied and result in different but reproducible particle arrangements and preferential contact orientations affecting the measured sound velocity. Interestingly, we find that the sound velocity increases when the magnetic field is applied parallel to the sound propagation direction and decreases when the magnetic field is applied perpendicular to the sound propagation direction. The observed qualitative relationship between the changes in the particle arrangement and the sound velocity is analyzed theoretically based on an effective medium theory adapted to account for the effect of the magnetic field in the preparation procedure and its influence on the medium contact fabric.