All-polarization-maintaining, self-starting Erbium-doped fiber laser based on graphene-saturable absorber is presented. Scalar soliton pulses with 570 fs duration and 114.1 MHz repetition rate were achieved at a 1557 nm center wavelength and with 6 nm bandwidth. The graphene-saturable absorber was formed by mechanical exfoliation of pure graphite. The laser was environmentally stable and could operate for long periods of time with linearly polarized output and degree of polarization at the level of 98%.