Proton-exchange membrane fuel cells (PEMFCs) are low-temperature fuel cells that have excellent starting performance due to their low operating temperature, can respond quickly to frequent load fluctuations, and can be manufactured in small packages. Unlike existing studies that mainly used hydrogen as fuel for PEMFCs, in this study, methane is used as fuel for PEMFCs to investigate its performance and economy. Methane is a major component of natural gas, which is more economically competitive than hydrogen. In this study, methane gas is reformed by the steam reforming method and is applied to the following five gas post-treatment systems: (a) Case 1—water–gas shift only (WGS), (b) Case 2—partial oxidation reforming only (PROX), (c) Case 3—methanation only, (d) Case 4—WGS + methanation, (e) Case 5—WGS + PROX. In the evaluation, the carbon monoxide concentration in the gas did not exceed 10 ppm, and the methane component, which has a very large greenhouse effect, was not regenerated in the post-treated exhaust gas. As a result, Case 5 (WGS and PROX) is the only case that satisfied both criteria. Therefore, we propose Case 5 as an optimized post-treatment system for methane reforming gas in ship PEMFCs.