We report an all-fiber, all-polarization maintaining (PM) ultrafast Tm-doped fiber laser mode-locked by a multilayer graphene-based saturable absorber (SA). The laser emits 603 fs-short pulses centered at 1876 nm wavelength with 6.6 nm of bandwidth and 41 MHz repetition rate. Graphene used as saturable absorber was obtained via chemical vapor deposition (CVD) on copper substrate and immersed in a poly(methylmethacrylate) (PMMA) support, forming a stable, free-standing foil containing 12 graphene layers, suitable for the use in a fiber laser. The generated 603 fs pulses are the shortest reported pulses achieved from a Tm-doped laser mode-locked by graphene saturable absorber so far. Additionally, this is the first demonstration of an all-PM Tm-doped fiber laser incorporating a graphene-based SA. Such cost-effective, compact and stable fiber lasers might be considered as sources usable in nonlinear frequency conversion, mid-infrared spectroscopy and remote sensing.