Estimating the dynamic status parameters of a battery, such as its state of health (SoH) and remaining useful life (RUL), is still a very difficult and complex task. In this paper we perform a structured review of the most relevant state of the art models, algorithms and commercial devices employed in the estimation of the SoH/RUL battery performance figures, in the context of embedded applications. The models and estimation techniques are thoroughly classified and, for each taxonomy class, a presentation of the working principles is made. A comprehensive set of metrics is then introduced for the evaluation of the SoH/RUL estimation techniques from the perspective of their implementation and operation efficiency in embedded systems. These algorithms are then analyzed and discussed in a comparative manner, with concrete figures and results. The capability and the performance of the different types of off-the-shelf fuel gauges to estimate the battery SoH/RUL parameters are also evaluated in this paper. Copyright (C) 2016 John Wiley & Sons, Ltd.