Digital signal processing, holography, and quantum and classical information processing rely heavily upon recording the amplitude and phase of coherent optical signals. One method for achieving coherent information storage makes use of electromagnetically induced transparency. Storage is achieved by compressing the optical pulse using the steep dispersion of the electromagnetically induced transparency medium and then mapping the electric field to local atomic quantum-state superpositions. Here we show that nonlinear optical processes may enhance pulse compression and storage, and that information about the nonlinear process itself may be stored coherently. We report on a pulse storage scheme in hot atomic rubidium vapour, in which a four-wave-mixing normal mode is stored using a double-Lambda configuration. The entire (broadened) waveform of the input signal is recovered after several hundred microseconds (1/e time of about 120 mu s), as well as a new optical mode (idler) generated from the four-wave-mixing process.