From measurements of fluctuation spectroscopy and weak nonlinear transport on the semimetallic ferromagnet EuB$_6$ we find direct evidence for magnetically-driven electronic phase separation consistent with the picture of percolation of magnetic polarons (MP), which form highly conducting magnetically-ordered clusters in a paramagnetic and poorly conducting background. These different parts of the conducting network are probed separately by the noise spectroscopy/nonlinear transport and the conventional linear resistivity. We suggest a comprehensive and universal scenario for the MP percolation, which occurs at a critical magnetization either induced by ferromagnetic order at zero field or externally applied magnetic fields in the paramagentic region.