Energy storage battery state of charge (SOC) estimation is an important task with practical applications, such as in electrical vehicles. However, existing SOC methods are not very intelligent and effective in achieving nonlinear models with potentially good interpretability. To address this, this paper proposes a genetic programming (GP)-based approach to automatically learning models for estimating battery state of charge. The proposed method eliminates the need for a predefined model structure and can automatically identify the optimal model structure and coefficients, outputting mathematical expressions that satisfy nonlinear and interpretable features. Experimental results demonstrate that the proposed approach outperforms the most commonly used linear regression method on a real dataset. With a flexible framework and good global search ability, the proposed approach can be easily applied in battery management systems and other related systems.