In this paper, we present Lyapunov characterizations of the global asymptotic stability, the input-to-state stability (ISS), and the incremental input-to-state stability (delta-ISS) for discrete-time nonlinear systems with uncertain and time-varying time delays. We provide necessary and sufficient conditions for the global asymptotic stability and for the ISS and sufficient conditions for the delta-ISS, in terms of discrete-time Lyapunov-Krasovskii functionals. In particular, the Lyapunov characterization of the notion of delta-ISS is motivated by problems concerning the construction of discrete abstractions approximating discrete-time nonlinear systems. Uncertain and time-varying time delays occur very frequently, for instance, in networked control systems. Examples are included that illustrate the proposed methodologies.