Cellular information processing is generally attributed to the complex networks of genes and proteins that regulate cell behavior. It is still unclear, however, what are the main features of those networks that allow a cell to encode and interpret its ever changing environment. Here, we address this question by studying the computational capabilities of the transcriptional regulatory networks of five evolutionary distant organisms. We identify in all cases a cyclic recurrent structure, formed by a small core of genes, that is essential for dynamical encoding and information integration. The recent history of the cell is projected nonlinearly into this recurrent reservoir of nodes, where it is encoded by its transient dynamics, while the rest of the network forms a readout layer devoted to decode and interpret the high-dimensional dynamical state of the recurrent core. In that way, gene regulatory networks act as echo-state networks that perform optimally in standard memory-demanding tasks, with most of their memory residing in the recurrent reservoir. The biological significance of these results is analyzed in the particular case of the bacterium Escherichia coli. Our work thus suggests that recurrent nonlinear dynamics is a key element for the processing of complex time-dependent information by cells.