The electricity production of a thermal generator is often constrained by the available fuel supply. These fuel constraints impose a maximum bound on the energy output over multiple time periods. Fuel constraints are increasingly important in electricity markets, due to two main reasons. First, as more natural gas-fired generators join the deregulated market, there is often competition for natural gas supply from other sectors (e.g., residential and manufacturing heating). Second, as more environmental and emission regulations are being placed on fossil fuel-fired generators, fuel supply is becoming more limited. However, there are few studies that consider the fuel constraints in the unit commitment problem from the perspective of computational analysis. To address the challenge faced by an independent power producer with a limited fuel supply, we study a fuel-constrained self-scheduling unit commitment (FSUC) problem where the production decisions are coupled across multiple time periods. We provide a complexity analysis of the FSUC problem and conduct a comprehensive polyhedral study by deriving strong valid inequalities. We demonstrate the effectiveness of our proposed inequalities as cutting planes in solving various multistage stochastic FSUC problems.