In this paper, we consider a general class of nonlinear discrete-time systems described by their input-output (I/O) relationship. We first present the necessary and sufficient conditions for existence of a local observable state-space realization of the system and an explicit algorithm for computing it. In cases where the I/O map and its resulting realization are nonminimal, we formulate an algorithm for extracting its minimal realization whenever possible, The developed theory and algorithms are illustrated by means of several example.